Home Online Manual
Top
Back: PocklingtonLehmer
Forward: pFactor
FastBack: atkins_lib
FastForward: hyperel_lib
Up: crypto_lib
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

D.12.3.19 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:
 
LIB "crypto.lib";
bigint h=10;
bigint p=h^30+4;
PollardRho(p,5000,0);
==> [1]:
==>    2
==> [2]:
==>    157
==> [3]:
==>    18737561
==> [4]:
==>    84982068258408294013
See also: primefactors.