Modifications to the number field sieve
type: Item
instance of: scholarly article
title: Modifications to the number field sieve
zbMATH Open document ID: 0806.11071
DOI: 10.1007/BF00198464
author: Don Coppersmith
published in: Journal of Cryptology
publication date: 1995-02-13T00:00:00Z
review text: The number field sieve, due to Lenstra et al. and Buhler et al., is a routine for factoring integers. The running time of this algorithm is estimated at \(e^{1.923+ \sigma(1) (\log N)^{1/3} (\log\log N)^{2/3}}\), where \(N\) is the number to be factored and \(\sigma(1)\) tends to 0 as \(N\to\infty\). The paper gives a brief description of the sieve method and describes a modification which reuses the computations of the initial sieve to reduce the exponent in the running time expression from 1.923 to 1.902. Furthermore, the same ideas are used to describe a way to precompute tables which are useful in factoring any integers in a large range. Ignoring the cost of the precomputations, an individual integer can be factored in time \(e^{1.639+ \sigma(1) (\log N)^{1/3} (\log\log N)^{2/3}}\). This substantial decrease in the time for factoring integers could have implications for the choice of prime parameters in cryptography.
Mathematics Subject Classification ID: 11Y05
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 480520
zbMATH Keywords: factorization of integers
zbMATH Keywords: factoring algorithm
zbMATH Keywords: number field sieve
zbMATH Keywords: cryptography
MaRDI profile type: Publication
cites work: Q4273681
cites work: On a problem of Oppenheim concerning ''Factorisatio Numerorum''
cites work: Q5514677
cites work: Factoring integers with elliptic curves
cites work: Q3808150
cites work: Refined analysis and improvements on some factoring algorithms
cites work: Solving sparse linear equations over finite fields
description: scientific article; zbMATH DE number 480520