|
D.12.3.21 PollardRho
Procedure from library crypto.lib (see crypto_lib).
- Usage:
- PollardRho(n,k,allFactors); optional: PollardRho(n,k,allFactors,L);
L a list of the first k primes
- Return:
- a list of factors of n (which could be just n),if allFactors=0
a list of all factors of n ,if allFactors=1
- Note:
- probabilistic rho-algorithm of Pollard to find a factor of n in k loops.
Creates a sequence x_i such that (x_i)^2=(x_2i)^2 mod n for some i,
computes gcd(x_i-x_2i,n) to find a divisor. To define the sequence
choose x,a and define x_n+1=x_n^2+a mod n, x_1=x.
If allFactors is 1, it tries to find recursively all prime factors
using the Soloway-Strassen test.
Example:
See also:
primefactors.
|