Package de.tilman_neumann.jml.factor.pollardRho

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

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

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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.

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

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