Class PollardRhoBrentMontgomeryR64Mul63
java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.pollardRho.PollardRhoBrentMontgomeryR64Mul63
public class PollardRhoBrentMontgomeryR64Mul63 extends FactorAlgorithm
Brents's improvement of Pollard's Rho algorithm using Montgomery multiplication.
This version combines the Montgomery reducer R=2^64 with mul63(). It is significantly faster than
PollardRhoBrentMontgomery64 for N < 58 bits, because until that size the performance advantage of
mul63() vs. mul64() predominates the performance loss caused by errors in Montgomery multiplication.
Another small performance gain stems from the choice of polynomials:
x_(n+1) = x_n*(x_n + 1) is slightly faster than x_(n+1) = (x_n)^2 - c
because it does not need another reduction (mod N) after subtracting c.
-
Field Summary
Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
-
Constructor Summary
Constructors Constructor Description PollardRhoBrentMontgomeryR64Mul63()
-
Method Summary
Modifier and Type Method Description long
findSingleFactor(long N)
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.static long
montMul63(long a, long b, long N, long Nhat)
Montgomery multiplication of a*b mod n with regard to R=2^63.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
-
PollardRhoBrentMontgomeryR64Mul63
public PollardRhoBrentMontgomeryR64Mul63()
-
-
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
-
findSingleFactor
public long findSingleFactor(long N) -
montMul63
public static long montMul63(long a, long b, long N, long Nhat)Montgomery multiplication of a*b mod n with regard to R=2^63. ("mulredc63x" in Yafu)- Parameters:
a
-b
-N
-Nhat
- complement of N mod 2^63- Returns:
- Montgomery multiplication of a*b mod n
-
main
public static void main(java.lang.String[] args)Test. Test numbers: 3225275494496681 (52 bits) = 56791489 * 56791529 322527333642009919 (59 bits) = 567914891 * 567914909 3225273260887418687 (62 bits) = 567914891 * 5679148957- Parameters:
args
- ignored
-