home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / basic / compiler / ubasic / malm / bwppt1.ub next >
Encoding:
Text File  |  1990-08-22  |  953 b   |  24 lines
  1.  1060   *BWppt1(N,&F)
  2.  1070   ' Baillie-Wagstaff Lucas preudoprime test.  See their paper.
  3.  1080   ' We assume n is odd and >11.  D is chosen by method "A".
  4.  1090   ' F is 1 to indicate probable prime, 0 for composite, and -1 if
  5.  1100   ' N is a square.
  6.  1110   ' 5  June 1990.
  7.  1120   local Q,D=-3,Us=0,Um,Ub=1,Vs,Vb,Wn,J=-1,I,T
  8.  1130   dim Bit%(400)
  9.  1140   Wn=isqrt(N):if res=0 then F=-1:return endif
  10.  1150   repeat D=-sgn(D)*(abs(D)+2) until kro(D,N)<1
  11.  1155   if kro(D,N)=0 then F=0:return endif
  12.  1160   Q=(1-D)\4:Wn=N+1
  13.  1165   T=gcd(Q,N):if and{T>1,T<N} then F=0:return endif
  14.  1170   repeat inc J:Wn=Wn\2:Bit%(J)=res until Wn=0
  15.  1180   Wn=((N+1)\2)
  16.  1190   for I=J to 0 step -1
  17.  1200   Vs=(2*Ub-Us)@N:Vb=((Vs+D*Us)*Wn)@N
  18.  1210   Us=(Us*Vs)@N:Ub=(Ub*Vb)@N
  19.  1220   Um=(Ub+Q*Us)@N
  20.  1230   if Bit%(I) then Us=Um else Ub=Um endif
  21.  1240   next I
  22.  1250   if Us=0 then F=1 else F=0 endif
  23.  1260   return ' End of subroutine BWppt1.
  24.