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 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
-
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
-