The number of relations in the quadratic sieve algorithm
The subject of our study is the single large prime variation of the quadratic sieve algorithm. We derive a formula for the average numbers of complete and incomplete relations per polynomial, directly generated by the algorithm. The number of additional complete relations from the incomplete relations is then computed by a known formula. Hence practical hints for the optimal choice of the parameter values can be derived. We further compare theoretical estimates for the total number of smooth integers in an interval with countings in practice.
|Numerical Algorithms and Problems (acm F.2.1)|
|Factorization; primality (msc 11A51), Factorization (msc 11Y05)|
|Department of Numerical Mathematics [NM]|
Boender, H. (1996). The number of relations in the quadratic sieve algorithm. Department of Numerical Mathematics [NM]. CWI.