Class AParamGenerator02
java.lang.Object
de.tilman_neumann.jml.factor.siqs.poly.AParamGenerator02
- All Implemented Interfaces:
AParamGenerator
public class AParamGenerator02 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 AParamGenerator02(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
-
AParamGenerator02
public AParamGenerator02(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 interfaceAParamGenerator
-
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 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 java.math.BigInteger computeNextAParameter()- Specified by:
computeNextAParameter
in interfaceAParamGenerator
-
getBestQ
public double getBestQ()- Specified by:
getBestQ
in interfaceAParamGenerator
- Returns:
- approximate optimal size of q-parameters
-
getQCount
public int getQCount()- Specified by:
getQCount
in interfaceAParamGenerator
- Returns:
- number of primes
s
witha-parameter = q_1 * ... * q_s
-
getQArray
public int[] getQArray()- Specified by:
getQArray
in interfaceAParamGenerator
- Returns:
- the q-values that give the
a-parameter = q_1 * ... * q_s
-
getQTArray
public int[] getQTArray()- Specified by:
getQTArray
in interfaceAParamGenerator
- 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 interfaceAParamGenerator
-