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 class FactorAlgorithm
      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 class FactorAlgorithm
      Parameters:
      N - number to be factored.
      Returns:
      factor