.model flat,stdcall
option casemap:none
include C:\masm32\include\windows.inc
include C:\masm32\include\kernel32.inc
include C:\masm32\include\user32.inc
includelib kernel32.lib
includelib user32.lib
FermaAlgo proto :DWORD

invoke FermaAlgo,123456789
call ExitProcess

;Algoritm Fermat (optimized by the Svin) to find 2 close dividers
;In: Odd natural number.
;Out: Multipliers of number N or message that N is prime.
;Step1: Put x = [sqrt(n)], if x^2 = n, then x is divider of n
;and the algo stops. In other case increase X by 1
;and go to step 2
;Step2: If x = (n+1)/2, then n is prome, and algo stops ;
;in other case calculate y = sqrt(x^2 - n)
;???3: If y is natural (e.i. [y]^2 = x^2 - n), then n can be represented by
;(x+y)(x-y), and algo stops; in other case goto step 2
FermaAlgo proc num
;Stage1: Check if input is correct.
;Check case 0,1 ?nd 2,3
cmp num,4
mov eax,num
jnc @F
jmp [eax*4][offset jmptbl] ;handling1,2,3,0
@@: test eax,1
je @even
;Stage 2 - init of var and check for a full sqare
;Step2 compares ? against the same value (n+1)/2
so we calculate it and give it a personal reg
;edi = (n+1)/2
;x always is changed by 1 and also can be used to calculate near sq
;so we'll give it a "personal" reg too.
;esi = x
;and X^2-n cause X^2 progressing uninterruped ?nd n is constant for speed we do
;ecx = X^2 - n
;difference between (X^2-n) and (X+1)^2 - n the same as X^2 and (X+1)^2 and equal
;2X +1 'cause (X+1)^2 = X^2+2X+1
;Get first value of X = sqrt(n)
cr dw ?
fstcw cr
or cr,0000010000000000b ;round to -
fldcw cr
fild num
fistp sqrt
mov esi,sqrt ;init X
mov eax,sqrt ;X -> eax
mul eax ;eax ^ 2
cmp eax,num ;full sq?
je @fullsq
mov edi,num
lea ecx,[eax][esi*2][1] ;ecx = (X+1)^2
sub ecx,edi ;ecx = (X+1)^2 - n
inc edi
shr edi,1 ;edi = (n+1)/2
mov sqrt,esi
jmp init
mov sqrt,ecx
fild sqrt
fistp sqrt ;sqrt = sqrt(x^2-n)
mov eax,sqrt
lea edx,[ecx][eax] ;check for odd\even
test edx,1 ;if sum isn't even than sq isn;t natural for sure
jne @odd ;
mul eax ;and yet in ~ 50% not full sq "will pass" the test
cmp eax,ecx ;for this cases we'll do aditional test
je @found
lea ecx,[ecx][esi*2][1]

inc esi
cmp esi,edi

jne @again
jmptbl dd @case0,@case1,@Prime,@Prime
MsgPrime db 'It's prime number - ',13,10
db 'It can be divided only by itself and 1',0
TtlMsgPrime db "Prime",0
invoke MessageBox,0,offset MsgPrime,offset TtlMsgPrime,0
MsgZero db 'Number = 0. It's senceless to divide it',0
invoke MessageBox,0,offset MsgZero,0,0
Msg1 db "Number = 1. It can be divided only by itself",0
invoke MessageBox,0,offset Msg1,0,0
MsgEven db "Number is even",0
invoke MessageBox,0,offset MsgEven,0,0
mov eax,esi
mov edx,esi
jmp @out
mov eax,esi ;eax = X
mov edx,sqrt ;edx = Y
sub eax,edx ;a = X-Y
lea edx,[esi][edx] ;b = X+Y
tmpl db Multiplyers of %i',13,10
db '%i,%i',13,10
db 13,10,0
MsgFound db 'Multiplyers are found',0
buffer db 64 dup (?)
invoke wsprintf,offset buffer,offset tmpl,num,eax,edx
invoke MessageBox,0,offset buffer,offset MsgFound,0

FermaAlgo endp
end start

Alex, I set the code formatting options so that the source is easier to read.
Posted on 2001-12-24 08:35:47 by The Svin
if you are interested, i' ll release an asm bignum library soon. it will be a bit slow, but well =)
Posted on 2001-12-24 10:24:40 by roy

wow very very nice algorithm but i think i didnt understand the step2
x = (n+1)/2 ? if this equal why n is prime ?

and a stupid question this is the same fermat who invented the problem X^n+Y^n=Z^n (n>2), right ?
Posted on 2001-12-24 12:05:42 by eko
What we try is to represent an odd number as difference of two sq
We can represent to multipliers of n as n=a*b and a > b
and we can represent difference of two sq as (X+Y)*(X-Y)
so we can assume that a = (X+Y) and b = (X-Y)
Now what is Fermat algo about.
It tries to find closest multipliers. So through whole algo it increasing a and decrising b
Now what is the least possible value of b? It's 1.
And this means that if we get down to this value that the only possible multiplyers is N*1
Now what does it mean b = 1 in context of (X+Y)(X-Y) that means that X-Y=1
and that means X^2-Y^2 = 2X-1 or 2Y+1 'cause (X+1)^2=X^2+2X+1 and X^2+2X+1-X2=2X+1
in our case 'case X-Y=1 X will serve as (X+1) and Y as X for the above.
if b = 1 than a = n that means if (X-Y)=1 then n = 2X-1; 2X=n+1 ;X=(N+1)/2

I can try to write more detail proof for the algo.
The only problem is my English - I'm trapped each time I get to math terms in English.

Yes, it is the same Fermat. But a little bit + me :)
Posted on 2001-12-24 12:53:33 by The Svin
nice i liked IT keep bring us your wisdom

Posted on 2001-12-24 13:16:53 by eko
hi think there is abug . its not exacly a bug but
try to put in the aglo 10!+1 =3628801
you will get 223047,211831 = 4291338495 this happend becuase the unsign,the algo think that the number 375F01h is actully FFC8A0FF


Posted on 2001-12-25 08:14:46 by eko
I see... Thanks.
I think in this version it can be easily solved with changing the
num to qword, in the case it we not be treated as signed long
32 bit by fpu. The rest of the algo will work just with low dword of
the qword but loading to fpu as qword (with zero in the high dword).
Posted on 2001-12-26 23:22:58 by The Svin
I am a native english speaker from the US, and I know people HERE that don't speak their OWN language as well as you do Svin. A friend in Hollend, also makes apoligies in her E-mails for her english, She speaks German, Dutch, and probubly a few others. I understand her E-mails JUST fine, but I speak and write ONLY English, not being gifted at languages, I seem to be the one being apoligized to for MY lack! So Svin, when you think it is YOU who has a problem getting your point across, perhaps what is really the point, is I lack the versatility to Learn your language, AND you make an effort to learn mine. Who, in the sceme of things has gained. I in an effort to understand, learn your gift for Math, and Garner a little bit of phraseology of your language, who knows, perhaps in time, I will LEARN your language.

Posted on 2001-12-28 10:51:29 by Anunitu
Thanks, Anunitu.
I should stress that main problem is math terms.
Since in math terms explicity is the main base of notations.
Posted on 2002-01-13 23:08:22 by The Svin