home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
basic
/
compiler
/
ubasic
/
malm
/
bwppt2.ub
< prev
next >
Wrap
Text File
|
1990-08-22
|
1KB
|
34 lines
10 *BWppt2(N,&F)
20 ' Baillie-Wagstaff strong Lucas pseudoprime test. See their paper.
30 ' We assume n is odd and > 11. D is chosen by method "A*".
40 ' F is 1 to indicate probable prime, 0 for composite, and -1 if
50 ' N is a square.
60 ' 5 June 1990.
70 local P=1,Pinv,Q,Qq,D=-3,Us=0,Um,Ub=1,Vs,Vb,Wn,S,Wnn,J=-1,I
80 dim Bit%(400)
90 Wn=isqrt(N):if res=0 then F=-1:return endif
100 repeat D=-sgn(D)*(abs(D)+2) until kro(D,N)<1
110 if kro(D,N)=0 then F=0:return endif
120 Q=(1-D)\4:Wn=N+1:if Q=-1 then Q=5:P=5 endif
130 Wnn=gcd(Q,N):if and{Wnn>1,Wnn<N} then F=0:return endif
140 S=0:repeat inc S:Wn=Wn\2:until odd(Wn)
150 Wnn=Wn
160 repeat inc J:Wnn=Wnn\2:Bit%(J)=res until Wnn=0
170 Wnn=(N+1)\2:Pinv=modinv(P,N)
180 for I=J to 0 step -1
190 Vs=(2*Ub-P*Us)@N:Vb=((P*Vs+D*Us)*Wnn)@N
200 Us=(Us*Vs)@N:Ub=(Ub*Vb)@N
210 Um=((Ub+Q*Us)*Pinv)@N
220 if Bit%(I) then Us=Um else Ub=Um endif
230 next I
240 if Us=0 then F=1:return endif
250 Vs=(2*Ub-P*Us)@N
260 if Vs=0 then F=1:return endif
270 Qq=modpow(Q,Wn,N)
280 for I=1 to S-1
290 Vs=(Vs*Vs-2*Qq)@N
300 if Vs=0 then F=1:cancel for:return endif
310 Qq=(Qq*Qq)@N
320 next I
330 F=0:return ' End of subroutine BWppt2.