Class 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].
    Author:
    Tilman Neumann
    • Constructor Detail

      • PollardRhoBrent

        public PollardRhoBrent()
    • Method Detail

      • getName

        public String getName()
        Specified by:
        getName in class FactorAlgorithm
        Returns:
        The name of the algorithm, possibly including important parameters.
      • main

        public static void main​(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