Class TinyEcm64

java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.ecm.TinyEcm64

public class TinyEcm64
extends FactorAlgorithm
A port of Ben Buhrow's tinyecm.c (https://www.mersenneforum.org/showpost.php?p=521028&postcount=84) an ECM implementation for unsigned 64 bit integers. So far it works for inputs up to 62 bit, albeit not as fast as the C original. The (lack of an) assembler instruction to multiply two 64 bit integers seems to make a big impact here...
  • Nested Class Summary

    Nested Classes
    Modifier and Type Class Description
    static class  TinyEcm64.EcmResult  
  • Field Summary

    Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

    NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
  • Constructor Summary

    Constructors
    Constructor Description
    TinyEcm64()  
  • Method Summary

    Modifier and Type Method Description
    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)  
    static long montMul64​(long a, long b, long N, long Nhat)
    Montgomery multiplication of a*b mod n.
    void searchFactors​(FactorArguments args, FactorResult result)
    Try to find at least one factor of the given args.N, which is composite and odd.

    Methods inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

    factor, factor, getDefault

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • TinyEcm64

      public TinyEcm64()
  • Method Details

    • getName

      public java.lang.String getName()
      Specified by:
      getName in class FactorAlgorithm
      Returns:
      The name of the algorithm, possibly including important parameters.
    • 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
    • findSingleFactor

      public java.math.BigInteger findSingleFactor​(java.math.BigInteger N)
      Find a single factor of the given N, which is composite and odd.

      WARNING: tinyEcm's findSingleFactor() implementation is unstable when called with N having only small factors, like 735=3*5*7^2. In such cases, an suitable amount of trial division should be carried out before.
      Specified by:
      findSingleFactor in class FactorAlgorithm
      Parameters:
      N - number to be factored.
      Returns:
      factor
    • searchFactors

      public void searchFactors​(FactorArguments args, FactorResult result)
      Description copied from class: FactorAlgorithm
      Try to find at least one factor of the given args.N, which is composite and odd. This is a default implementation for algorithms that will only find a single factor or none at all. For sub-algorithms that may find more factors at once this method should be overwritten appropriately.
      Overrides:
      searchFactors in class FactorAlgorithm
      result - the result of the factoring attempt. Should be initialized only once by the caller to reduce overhead.
    • main

      public static void main​(java.lang.String[] args)