Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8896949 | Journal of Number Theory | 2018 | 68 Pages |
Abstract
Factorisation of integers n is of number theoretic and cryptographic significance. The Number Field Sieve (NFS) introduced circa 1990, is still the state of the art algorithm, but no rigorous proof that it halts or generates relationships is known. We propose and analyse an explicitly randomised variant. For each n, we show that these randomised variants of the NFS and Coppersmith's multiple polynomial sieve find congruences of squares in expected times matching the best-known heuristic estimates.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Jonathan D. Lee, Ramarathnam Venkatesan,