```
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 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:
http://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 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...

**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

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.