Pollard's Rho (Factoring n)

[michaeled314]

This is great code I dreamed up, if only I could have some help optimizing it:

It outputs a non-trivial factor of n (trivial if n is prime)

Code: Select all

Procedure.l gcd(a,b)
 While b <> 0
  t = b
  b = a % b
  a = t
 Wend
 ProcedureReturn a
EndProcedure

z.l = 0

For n = 2 To 1000
 x.l = 2
 y.l = 2
 d.l = 1
 While d=1
  x = (x*x+z)%n
  y = (y*y+z)%n
  y = (y*y+z)%n
  d = gcd(Int(Abs(x-y)),n)
  If d = n And z<100
   z+1
   d=1
  EndIf
  If d>1 And d<>n
   m=z
   z=1
  EndIf
 Wend
 Debug Str(d)+" divides "+Str(n)+"  (using z="+Str(m)+")"
Next