Pollard's Rho (Factoring n)
Posted: Wed May 06, 2009 11:11 pm
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)
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