Class PollardRho
java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.pollardRho.PollardRho
public class PollardRho extends FactorAlgorithm
From: http://www.cs.princeton.edu/introcs/79crypto/PollardRho.java
(INTRODUCTION TO COMPUTER SCIENCE by Robert Sedgewick and Kevin Wayne)
Pollards Rho method. Pollard's rho method is a randomized factoring algorithm
that can factor 128 bit numbers in a reasonable amount of time, especially if
the numbers have some small factors. It is based on the following fact: if d is
the smallest nontrivial factor of N and x - y is a nontrivial multiple of d then
gcd(x-y, N) = d. A naive method would be to generate a bunch of random values
x[1], x[2], ..., x[m] and compute gcd(x[i]-x[j], N) for all pairs i and j.
Pollard's rho method is an ingenious method way to find x and y without doing
all of the pairwise computations. It works as follows: choose a and b at random
between 1 and N-1, and initialize x = y = a. Repeatedly update x = f(x), y = f(f(y)),
where f(x) = x^2 + b as long as gcd(x-y, N) = 1. The gcd is a factor of N, but if you
get unlucky, it could be equal to N. By randomly choosing a and b each time, we
ensure that we never get too unlucky.
-
Field Summary
Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
-
Constructor Summary
Constructors Constructor Description PollardRho()
-
Method Summary
Modifier and Type Method Description java.math.BigInteger
findSingleFactor(java.math.BigInteger N)
Find a single factor of the given N, which is composite and odd.java.lang.String
getName()
Methods inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
factor, factor, getDefault, searchFactors
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Constructor Details
-
PollardRho
public PollardRho()
-
-
Method Details
-
getName
public java.lang.String getName()- Specified by:
getName
in classFactorAlgorithm
- Returns:
- The name of the algorithm, possibly including important parameters.
-
findSingleFactor
public java.math.BigInteger findSingleFactor(java.math.BigInteger N)Description copied from class:FactorAlgorithm
Find a single factor of the given N, which is composite and odd.- Specified by:
findSingleFactor
in classFactorAlgorithm
- Parameters:
N
- number to be factored.- Returns:
- factor
-