numlib::pollard -- Pollard's rho
factorization algorithm
Introductionnumlib::pollard(n, m) tries to find a
factor of n using m iterations of Pollard's
rho algorithm.
If m is missing, 10000 iterations are
carried out.
Call(s)numlib::pollard(n, <m>)
Parametersn,m |
- | positive integers |
Returnsnumlib::pollard returns n, a sequence of
two factors, or FAIL.
Related
Functionsifactor, numlib::ecm, numlib::mpqs
Detailsnumlib::pollard returns either n if
n is said to be prime by isprime, or
g,n/g if a factor g was found. If after
m iterations still no factor has been found,
FAIL is returned.
Example
1>> numlib::pollard(10000000019)
10000000019
>> numlib::pollard(278218430085289734806642953)
FAIL
>> numlib::pollard(278218430085289734806642953,10^5)
3486784409, 79792266297612017