Class AParamGenerator01
- java.lang.Object
-
- de.tilman_neumann.jml.factor.siqs.poly.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 isqCounta
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 Summary
Constructors Constructor Description AParamGenerator01(Integer wanted_qCount)
Full constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
cleanUp()
Release memory after a factorization.BigInteger
computeNextAParameter()
String
getName()
int[]
getQArray()
int
getQCount()
int[]
getQTArray()
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.
-
-
-
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
-
getName
public String getName()
- Specified by:
getName
in interfaceAParamGenerator
-
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 aqCount
value fixed throughout the rest of the factorization of N.- Specified by:
initialize
in interfaceAParamGenerator
d
- the d-value in Q(x) = (d*a*x + b)^2 - kN; typically 1 or 2tArray
- the modular square roots t with t^2 == kN (mod p)
-
computeNextAParameter
public BigInteger computeNextAParameter()
- Specified by:
computeNextAParameter
in interfaceAParamGenerator
-
getQCount
public int getQCount()
- Specified by:
getQCount
in interfaceAParamGenerator
- Returns:
- number of primes
s
witha-parameter = q_1 * ... * q_s
-
getQTArray
public int[] getQTArray()
- Specified by:
getQTArray
in interfaceAParamGenerator
- Returns:
- the modular sqrt values for the chosen q's.
-
getQArray
public int[] getQArray()
- Specified by:
getQArray
in interfaceAParamGenerator
- Returns:
- the q-values that give the
a-parameter = q_1 * ... * q_s
-
cleanUp
public void cleanUp()
Description copied from interface:AParamGenerator
Release memory after a factorization.- Specified by:
cleanUp
in interfaceAParamGenerator
-
-