Class PollardRhoBrentMontgomery64_MH
java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.pollardRho.PollardRhoBrentMontgomery64_MH
public class PollardRhoBrentMontgomery64_MH extends FactorAlgorithm
Brents's improvement of Pollard's Rho algorithm using Montgomery multiplication.
The main reason why Montgomery multiplication is helpful for Pollard-Rho is that
no conversions to/from Montgomery form are required.
In this implementation I managed to use the Montgomery reducer R=2^64, which simplifies
the Montgomery multiplication a good deal.
Another small performance improvement stems from using the polynomial x*(x+1) instead of x^2+c,
which saves us the addition modulo N after each Montgomery multiplication.
This variant of PollardRhoBrentMontgomery64 uses Math.multiplyHigh().
It is about factor 1.4 faster than without if intrinsics for that function are supported.
Typically this requires Java 10 and not too oldish hardware.
-
Field Summary
Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm
NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
-
Constructor Summary
Constructors Constructor Description PollardRhoBrentMontgomery64_MH()
-
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
montMul64(long a, long b, long N, long Nhat)
Montgomery multiplication of a*b mod n.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
-
PollardRhoBrentMontgomery64_MH
public PollardRhoBrentMontgomery64_MH()
-
-
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) -
montMul64
public static long montMul64(long a, long b, long N, long Nhat)Montgomery multiplication of a*b mod n. ("mulredcx" in Yafu)- Parameters:
a
-b
-N
-Nhat
- complement of N mod 2^64- 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
-