OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE
Factor PROC num:DWORD
invoke Sqrt, [esp][4] ; num
xor edx, edx
test eax, 1
sete dl
sub eax, edx
mov ecx, eax
mul eax
lea edx, [ecx*2]
mov ecx, [esp][4]
sub ecx, eax
mov eax, edx
_0: cmp ecx, eax
jnc _1
sub eax, 4
add ecx, edx
_1: add edx, 4
sub ecx, eax
jne _0
shr eax, 1
shr edx, 1
retn 4
Factor ENDPhttp://www.asmcommunity.net/board/viewtopic.php?p=155261#155261
Factor does not work for even numbers.
invoke Factor, 4093*2053
; EAX = 2053
; EDX = 4093
It is left as an exercise for others to explain how it works.
A prime array could be used to end recursion early. I am developing a more advanced version for larger numbers. I would appreciate credit being given for it's use.
That was very clever! Alas, it doesn't seem to be extendible to large numbers (or maybe I'm not thinking hard enough?) If you could do that, that would be impressive.
Let me just tidy it up a bit:
If you'd like, you could get rid of the imul, and get the remainder from instead, but then you have to pay attention to the lower bit...
Let me just tidy it up a bit:
OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE
Factor PROC num:DWORD
push ebx
mov ebx, [esp+8]
invoke Sqrt, ebx
dec eax
or al, 1
lea edx, [eax+eax]
imul eax,eax
sub ebx,eax
mov eax, edx
_0: cmp ebx, eax
jnc _1
sub eax, 4
add ebx, edx
_1: add edx, 4
sub ebx, eax
jne _0
shr eax, 1
shr edx, 1
pop ebx
retn 4
Factor ENDPIf you'd like, you could get rid of the imul, and get the remainder from instead, but then you have to pay attention to the lower bit...
Sephiroth3, thank you. You are correct if you mean the Sqrt function creates the 'residue' we need for factoring - needing no IMUL - it is best to combine them into one function. The algorithm certainly does extend to very large integers (have factored 915942972447382947582161328343629860183 in lessthan an hour), but I have other improvements to make it much faster! :)
Long way to go compared to the Elliptic Curve Method. :P
Long way to go compared to the Elliptic Curve Method. :P
It took only 2s using that Java applet :-D
This method is faster than: a^2 - b^2 = (a+b)(a-b) ...also called the Fermat Factoring Method. We have a composite (m) and are searching for two factors (p) and (q):
m = pq
p - q = 2c
d = p - c
pq = (d + c)(d - c) = d^2 - c^2
assume c=0
d0 <= Ceiling(m^0.5)
dN = d(N-1) + 1
cN = (dN^2 - m)^0.5
N<=N+1, until cN is an integer
Can someone show the two methods to be the same?
m = pq
p - q = 2c
d = p - c
pq = (d + c)(d - c) = d^2 - c^2
assume c=0
d0 <= Ceiling(m^0.5)
dN = d(N-1) + 1
cN = (dN^2 - m)^0.5
N<=N+1, until cN is an integer
Can someone show the two methods to be the same?
Hey Bitrake,
I was reading somewhere that fermat factoring might be even slower than trial divisons if the factors are small. I guess this method of factoring is only for factors that you know are close to the squareroot of the number you are factoring.
Regards,
Victor
I was reading somewhere that fermat factoring might be even slower than trial divisons if the factors are small. I guess this method of factoring is only for factors that you know are close to the squareroot of the number you are factoring.
Regards,
Victor
roticv, yes, Fermat Factoring is very slow - doesn't it make you wonder how the method was used by Fermat? I don't think Fermat was as verbose as we would have liked him to be.
bitrake, it is sad that fermat does not document his findings and always give excuses for not doing so. :-D Just a question, say I want to code my own maths library for big numbers, should I store the numbers as binary data or store each digit (base 10) as a byte or nibble. What is your opinion? Which would be faster?
Different representations have different uses, but in general storing the number as binary data is faster and takes less space. I've also been playing with algorithms operating on the base two exponents (example: 5 = (DWORD 2, DWORD 0)), but it takes a lot of space and has limited use.