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