Class PollardRhoBrent

java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.pollardRho.PollardRhoBrent

public class PollardRhoBrent
extends FactorAlgorithm
Brents's improvement of Pollard's Rho algorithm, following [Richard P. Brent: An improved Monte Carlo Factorization Algorithm, 1980].
  • Field Summary

    Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

    NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
  • Constructor Summary

    Constructors
    Constructor Description
    PollardRhoBrent()  
  • 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()  
    static void main​(java.lang.String[] args)
    Test.

    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

    • PollardRhoBrent

      public PollardRhoBrent()
  • 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
    • main

      public static void main​(java.lang.String[] args)
      Test. Some test numbers:
      5679148659138759837165981543 = 450469808245315337 * 466932157 * 3^3, takes ~250 ms
      54924524576914518357355679148659138759837165981543 = 1557629117554716582307318666440656471 * 35261619058033, takes ~ 4s
      F6 = 18446744073709551617 = 274177 * 67280421310721 takes ~166ms
      F7 = 2^128 + 1 = 340282366920938463463374607431768211457 = 5704689200685129054721 * 59649589127497217; Hard for Pollard-Rho-Brent (~ 173-414s) , easy for CFrac or ECM
      F8 = 115792089237316195423570985008687907853269984665640564039457584007913129639937 = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321, takes ~141s
      8225267468394993133669189614204532935183709603155231863020477010700542265332938919716662623 = 1234567891 * 1234567907 * 1234567913 * 1234567927 * 1234567949 * 1234567967 * 1234567981 * 1234568021 * 1234568029 * 1234568047, takes about 300 ms
      101546450935661953908994991437690198927080333663460351836152986526126114727314353555755712261904130976988029406423152881932996637460315302992884162068350429 = 123456789012419 * 123456789012421 * 123456789012437 * 123456789012439 * 123456789012463 * 123456789012521 * 123456789012523 * 123456789012533 * 123456789012577 * 123456789012629 * 123456789012637, takes about 147s
      Parameters:
      args - ignored