Interface AParamGenerator

  • All Known Implementing Classes:
    AParamGenerator01

    public interface AParamGenerator
    Interface for generators that produce the leading coefficient a 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. The quality of the a-generator is crucial for both stability and performance of SIQS.
    Author:
    Tilman Neumann
    • Method Detail

      • initialize

        void initialize​(int k,
                        BigInteger N,
                        BigInteger kN,
                        int d,
                        int primeBaseSize,
                        int[] primesArray,
                        int[] tArray,
                        int sieveArraySize)
        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.
        Parameters:
        k -
        N -
        kN -
        d - the d-value in Q(x) = (d*a*x + b)^2 - kN; typically 1 or 2
        primeBaseSize -
        primesArray -
        tArray - the modular square roots t with t^2 == kN (mod p)
        sieveArraySize -
      • computeNextAParameter

        BigInteger computeNextAParameter()
      • getQCount

        int getQCount()
        Returns:
        number of primes s with a-parameter = q_1 * ... * q_s
      • getQArray

        int[] getQArray()
        Returns:
        the q-values that give the a-parameter = q_1 * ... * q_s
      • getQTArray

        int[] getQTArray()
        Returns:
        the modular sqrt values for the chosen q's.
      • cleanUp

        void cleanUp()
        Release memory after a factorization.