Class SIQS_Small

java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.siqs.SIQS_Small

public class SIQS_Small
extends FactorAlgorithm
Single-threaded SIQS implementation used to factor the Q(x)-rests in the trial division stage of SIQS/PSIQS. So far, the main purpose of this class is to prevent excessive logging when GlobalFactoringOptions.ANALYZE == true and SIQS trial division starts to use an nested SIQS to factor large Q rests. A second purpose would be to optimize this class for the factorization of small N (say, below 100 bit), but little effort has been dedicated to that so far.
  • Field Summary

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

    NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
  • Constructor Summary

    Constructors
    Constructor Description
    SIQS_Small​(float Cmult, float Mmult, java.lang.Integer wantedQCount, SIQSPolyGenerator polyGenerator, int extraCongruences, boolean permitUnsafeUsage)
    Standard constructor.
  • Method Summary

    Modifier and Type Method Description
    void cleanUp()  
    java.math.BigInteger findSingleFactor​(java.math.BigInteger N)
    Test the current N.
    java.lang.String getName()  
    static void main​(java.lang.String[] args)
    Stand-alone test.
    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

    • SIQS_Small

      public SIQS_Small​(float Cmult, float Mmult, java.lang.Integer wantedQCount, SIQSPolyGenerator polyGenerator, int extraCongruences, boolean permitUnsafeUsage)
      Standard constructor.
      Parameters:
      Cmult - multiplier for prime base size
      Mmult - multiplier for sieve array size
      wantedQCount - the wanted number of q whose product gives the a-parameter
      polyGenerator -
      extraCongruences - the number of surplus congruences we collect to have a greater chance that the equation system solves.
      permitUnsafeUsage - if true then SIQS_Small uses a sieve exploiting sun.misc.Unsafe features. This may be ~10% faster.
  • Method Details

    • getName

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

      public java.math.BigInteger findSingleFactor​(java.math.BigInteger N)
      Test the current N.
      Specified by:
      findSingleFactor in class FactorAlgorithm
      Parameters:
      N - number to be factored.
      Returns:
      factor, or null if no factor was found.
    • cleanUp

      public void cleanUp()
    • main

      public static void main​(java.lang.String[] args)
      Stand-alone test.
      Parameters:
      args - ignored Some test numbers: 11111111111111111111111111 5679148659138759837165981543 11111111111111111111111111155555555555111111111111111 2900608971182010301486951469292513060638582965350239259380273225053930627446289431038392125 = 33333 * 33335 * 33337 * 33339 * 33341 * 33343 * 33345 * 33347 * 33349 * 33351 * 33353 * 33355 * 33357 * 33359 * 33361 * 33363 * 33367 * 33369 * 33369 * 33371 15841065490425479923 = 2604221509 * 6082841047