Rigorous Analysis of a Randomised Number Field Sieve
Preprint
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.
Keywords
All Related Versions
- Version 1, 2018-05-22, ArXiv
- Published version: Journal of Number Theory, 187, 92.
This publication has 23 references indexed in Scilit:
- On a paper of K. Soundararajan on smooth numbers in arithmetic progressionsJournal of Number Theory, 2012
- On polynomial selection for the general number field sieveMathematics of Computation, 2006
- Subquadratic Computation of Vector Generating Polynomials and Improvement of the Block Wiedemann AlgorithmJournal of Symbolic Computation, 2002
- Modifications to the Number Field SieveJournal of Cryptology, 1993
- Integers, without large prime factors, in arithmetic progressions, IActa Mathematica, 1993
- On the number of positive integers ≦ x and free of prime factors > yJournal of Number Theory, 1986
- On a problem of Oppenheim concerning “factorisatio numerorum”Journal of Number Theory, 1983
- Quelques applications du théorème de densité de ChebotarevPublications mathématiques de l'IHÉS, 1981
- Some effective cases of the Brauer-Siegel TheoremInventiones Mathematicae, 1974
- Neuer Beweis des Primzahlsatzes und Beweis des PrimidealsatzesMathematische Annalen, 1903