An Implementation of the Number Field Sieve

1 January 1996

journal article
research article
Published by Taylor & Francis in Experimental Mathematics

Vol. 5 (3) , 231-253
https://doi.org/10.1080/10586458.1996.10504590

Abstract

The Number Field Sieve (NFS) is the asymptotically fastest known factoring algorithm for large integers. This article describes an implementation of the NFS, including the choice of two quadratic polynomials, both classical sieving and a special form of lattice sieving (line sieving), the block Lanczos method and a new square root algorithm. Finally some data on factorizations obtained with this implementation are listed, including the record factorization of 12¹⁵¹ – 1.

Keywords

This publication has 18 references indexed in Scilit:

The Quadratic Sieve Factoring Algorithm
Published by Springer Nature ,2000
Square roots of products of algebraic numbers
Published by American Mathematical Society (AMS) ,1994
Solving linear equations over GF(2): block Lanczos algorithm
Linear Algebra and its Applications, 1993
The factorization of the ninth Fermat number
Mathematics of Computation, 1993
Factoring integers with the number field sieve
Published by Springer Nature ,1993
Computing a square root for the number field sieve
Lecture Notes in Mathematics, 1993
The lattice sieve
Published by Springer Nature ,1993
The number field sieve
Lecture Notes in Mathematics, 1993
Factoring with cubic integers
Lecture Notes in Mathematics, 1993
Factoring polynomials with rational coefficients
Mathematische Annalen, 1982