On the amount of sieving in factorization methods

Leiden Repository

On the amount of sieving in factorization methods

Type: Doctoral Thesis
Title: On the amount of sieving in factorization methods
Author: Ekkelkamp, Willemina Hendrika
Publisher: Faculty of Science, Leiden University
Issue Date: 2010-01-20
Keywords: Density
Factoring
Multiple polynomial quadratic sieve
Number field sieve
Number theory
Simulation
Abstract: 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.
Description: Promotoren: R. Tijdeman, A.K. Lenstra, Co-promotor: H.J.J. te Riele
With summary in Dutch
Faculty: Faculteit der Wiskunde en Natuurwetenschappen
Citation: Ekkelkamp, W.H., 2010, Doctoral thesis, Leiden University
ISBN: 9789061965541
Handle: http://hdl.handle.net/1887/14567
 

Files in this item

Description Size View
application/pdf Propositions 43.62Kb View/Open
application/pdf Full text 1.110Mb View/Open

This item appears in the following Collection(s)