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

Class AParamGenerator01

  • All Implemented Interfaces:
    AParamGenerator
    public class AParamGenerator01
extends 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.
    Author:
    Tilman Neumann

    • Constructor Detail

      • AParamGenerator01

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

    • Method Detail

      • initialize

        public void initialize​(int k,
                       BigInteger N,
                       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)

      • getQCount

        public int getQCount()
        Specified by:
        getQCount in interface AParamGenerator
        Returns:
        number of primes s with 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.

      • getQArray

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