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].- Author:
- Tilman Neumann
-
-
Field Summary
-
Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
DEFAULT, NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
-
-
Constructor Summary
Constructors Constructor Description PollardRhoBrent()
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description BigInteger
findSingleFactor(BigInteger N)
Find a single factor of the given N, which is composite and odd.String
getName()
static void
main(String[] args)
Test.-
Methods inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
factor, factor, searchFactors
-
-
-
-
Method Detail
-
getName
public String getName()
- Specified by:
getName
in classFactorAlgorithm
- Returns:
- The name of the algorithm, possibly including important parameters.
-
findSingleFactor
public BigInteger findSingleFactor(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
- Returns:
- factor
-
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
-
-