home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / basic / compiler / ubasic / malm / mppt.ub < prev    next >
Encoding:
Text File  |  1990-08-22  |  892 b   |  22 lines
  1.  1090   *Mppt(N,Q,&F)
  2.  1100   ' Probabilistic test of Malm for primality (or compositeness).
  3.  1110   ' Assumes N is odd, not a square, and that (Q|N)=1.  Returns F=1
  4.  1120   ' if N is a probable prime, and F=0 if N is composite.
  5.  1130   ' 8 June 1990.
  6.  1140   dim Bit%(400)
  7.  1150   local Nw,P=1,Vs,Vb,Vm,D,T,Ta,I,J=-1
  8.  1160   Nw=(N+1)\2
  9.  1170   repeat inc P:D=(P*P-4*Q):Ta=gcd(D,N)
  10.  1180   until or{kro(D,N)=-1,and{Ta>1,Ta<N}}
  11.  1190   if and{Ta>1,Ta<N} then F=0:return endif
  12.  1200   repeat inc J:Nw=Nw\2:Bit%(J)=res until Nw=0
  13.  1210   Vs=P:Vb=(P*Vs-2*Q)@N:T=Q
  14.  1220   for I=J-1 to 0 step -1
  15.  1230   Ta=2*T
  16.  1240   if Bit%(I)=0 then Vb=(Vs*Vb-P*T)@N:Vs=(Vs*Vs-Ta)@N:T=(T*T)@N
  17.  1250   :else Vs=(Vs*Vb-P*T)@N:Vb=(Vb*Vb-Q*Ta)@N:T=(T*T*Q)@N endif
  18.  1270   next I
  19.  1280   Vs=(Vs*Vs)@N:Ta=(4*Q)@N
  20.  1290   if Vs=Ta then F=1 else F=0 endif
  21.  1300   return ' End of subroutine Mppt.
  22.