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 ENDP
The above algorithm only finds two factors of a number (EAX and EDX on return). If EAX is equal to one then EDX is prime, else call Factor recursively on EAX and EDX. Yes, in general it is faster than trial division and does not need an array of primes! Please, see the other thread for SquareRoot algorithm:

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.
Posted on 2005-01-17 16:59:59 by bitRAKE
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:


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 ENDP

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...
Posted on 2005-01-18 18:03:33 by Sephiroth3
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
Posted on 2005-01-19 19:24:26 by bitRAKE
It took only 2s using that Java applet :-D
Posted on 2005-01-20 04:03:12 by roticv
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?
Posted on 2005-01-20 23:57:16 by bitRAKE
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.

Posted on 2005-02-13 10:25:28 by roticv
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.
Posted on 2005-02-15 00:52:26 by bitRAKE
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?
Posted on 2005-02-15 07:12:35 by roticv
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.
Posted on 2005-02-15 19:04:02 by bitRAKE