Proefschrift
On the amount of sieving in factorization methods
Promotoren: R. Tijdeman, A.K. Lenstra, Co-promotor: H.J.J. te Riele
- Auteur
- W.H. Ekkelkamp
- Datum
- 02 januari 2010
- Links
- Thesis in Leiden Repository
Factorization methods, such as the quadratic sieve and the number field sieve, spend a lot of time on the sieving step, in which the necessary relations are collected for factoring the given number N. Relations are smooth or k-semismooth numbers (numbers with either all prime factors below some bound or all with the exception of at most k prime factors that do not exceed a second bound) or pairs of these type of numbers. In this thesis, we predict the amount of k-semismooth numbers needed to factor N, based on asymptotic approximation formulas (these formulas generalize the published results), and compare them with the amount of k-semismooth numbers found during the factorization of N. Furthermore, for the number field sieve we propose a method for predicting the number of necessary relations for factoring N with given parameters, and the corresponding sieving time. The basic idea is to do a small but representative amount of sieving and analyze the relations in this sample. We randomly generate relations according to the relevant distribution as observed in the sample and process these relations. Experiments show that our predictions of the number of necessary relations are within 2% of the number of relations needed in the real factorization.