Advanced Search

Question: Pollard's P-1 Factorisation

Question:Pollard's P-1 Factorisation

Declan 20 Maple 2015
March 30 2016
0

I'm trying to write a procedure that computes Pollard's P-1 Method for a given integer n, and then outputs the prime factorisation of n.

Here is what I have so far:

Pollard := proc (n)
local i, r, g;
r[1] := `mod`(2^factorial(2), n);
for i from 2 while gcd(`mod`(r[i-1]-1, n), n) = 1 do
r[i] := `mod`(2^factorial(i+1), n) end do;
g[i] := gcd(`mod`(r[i-1]-1, n), n);
if g[i] < n then return g[i]
else return n
end if
end proc;

But my procedure doesn't seem to work for a lot of large values for n.
And also I can't figure out how to make it actually output the factorisation.

Any help would be appreciated.
Please Wait...