Package de.tilman_neumann.jml.factor.siqs.poly

Class AParamGenerator01

java.lang.Object
de.tilman_neumann.jml.factor.siqs.poly.AParamGenerator01
All Implemented Interfaces:
AParamGenerator
public class AParamGenerator01
extends java.lang.Object
implements AParamGenerator
Generator for the a-parameter (or "hypercube"), which is the leading coefficient of the quadratic polynomial Q(x) = (d*a*x+b)^2 - kN used by SIQS. d is typically 1 or 2.

The a-parameter in SIQS is chosen as a product of primes from the prime base: a = q1 * ... * q_s. Its value should be roughly a ~ sqrt(2*k*N)/(d*M), where M is the sieve array size, such that |Q(x)| is about the same at x=+M and x=-M, and |Q(x)| <= kN for all x. One consequence of this choice is that about 70% of the Q we get are negative. But trying to correct that means bigger values for positive Q and slows down the QS. As suggested by [Carrier/Wagstaff], it is important to avoid q_l that divide k. Otherwise for many N we would require a big number of solver runs. This class does not implement the standard-procedure due to [Carrier/Wagstaff] for two reasons: 1. I wanted to test which size of the q_l is actually the best. It turned out that the q_l should be rather large and qCount rather small. 2. Splitting the prime base and {q_l} into three sets feels like introducing some unnecessary complexity to the code. The algorithm used here is mostly random, choosing the q_l from a range of about the wanted size. The last q_l is chosen deterministically such that the best a-parameter is matched as close as possible. Therefore the algorithm is not stable for N < 50 bit, but faster for bigger N. The expected best a-value is approximated quite accurately. A very important parameter is qCounta and thus which average factor size is most appropriate for given magnitudes of kN. A minimum value of qCount==4 gives best stability at small N, down to 53 bits. Since 2016-12-15, entries of qArray and qIndexArray are sorted bottom-up. Since 2018-02-13, the d-parameter was introduced.

  • Constructor Summary

    Constructors
    Constructor Description
    AParamGenerator01​(java.lang.Integer wanted_qCount)
    Full constructor.

  • Method Summary

    Modifier and Type Method Description
    void cleanUp()
    Release memory after a factorization.
    java.math.BigInteger computeNextAParameter()  
    double getBestQ()  
    java.lang.String getName()  
    int[] getQArray()  
    int getQCount()  
    int[] getQTArray()  
    void initialize​(int k, java.math.BigInteger N, java.math.BigInteger kN, int d, int primeBaseSize, int[] primesArray, int[] tArray, int sieveArraySize)
    Initialize this a-parameter generator for a new N.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • AParamGenerator01

      public AParamGenerator01​(java.lang.Integer wanted_qCount)
      Full constructor.
      Parameters:
      wanted_qCount - the wanted number of factors of the a-parameter; null for automatic selection

  • Method Details

    • getName

      public java.lang.String getName()
      Specified by:
      getName in interface AParamGenerator

    • initialize

      public void initialize​(int k, java.math.BigInteger N, java.math.BigInteger kN, int d, int primeBaseSize, int[] primesArray, int[] tArray, int sieveArraySize)
      Description copied from interface: AParamGenerator
      Initialize this a-parameter generator for a new N. One result has to be a qCount value fixed throughout the rest of the factorization of N.
      Specified by:
      initialize in interface AParamGenerator
      d - the d-value in Q(x) = (d*a*x + b)^2 - kN; typically 1 or 2
      tArray - the modular square roots t with t^2 == kN (mod p)

    • computeNextAParameter

      public java.math.BigInteger computeNextAParameter()
      Specified by:
      computeNextAParameter in interface AParamGenerator

    • getBestQ

      public double getBestQ()
      Specified by:
      getBestQ in interface AParamGenerator
      Returns:
      approximate optimal size of q-parameters

    • getQCount

      public int getQCount()
      Specified by:
      getQCount in interface AParamGenerator
      Returns:
      number of primes s with a-parameter = q_1 * ... * q_s

    • getQArray

      public int[] getQArray()
      Specified by:
      getQArray in interface AParamGenerator
      Returns:
      the q-values that give the a-parameter = q_1 * ... * q_s

    • getQTArray

      public int[] getQTArray()
      Specified by:
      getQTArray in interface AParamGenerator
      Returns:
      the modular sqrt values for the chosen q's.

    • cleanUp

      public void cleanUp()
      Description copied from interface: AParamGenerator
      Release memory after a factorization.
      Specified by:
      cleanUp in interface AParamGenerator