Class PollardRhoBrentMontgomery64_MHInlined

java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.pollardRho.PollardRhoBrentMontgomery64_MHInlined

public class PollardRhoBrentMontgomery64_MHInlined
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_MHInlined()  
  • 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_MHInlined

      public PollardRhoBrentMontgomery64_MHInlined()
  • 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)
    • 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