Matthew Briggs' 'An Introduction to the Number Field Sieve' is
a very good introduction; it's heavier than C&P in places
and lighter in others
Michael Case's 'A Beginner's Guide to the General Number Field
Sieve' has more detail all around and starts to deal with
advanced stuff
Per Leslie Jensen's thesis 'Integer Factorization' has a lot of
introductory detail on NFS that other references lack
Peter Stevenhagen's "The Number Field Sieve" is a whirlwind
introduction the algorithm
Steven Byrnes' "The Number Field Sieve" is a good simplified
introduction as well.
Lenstra, Lenstra, Manasse and Pollard's paper 'The Number Field
Sieve' is nice for historical interest
'Factoring Estimates for a 1024-bit RSA Modulus' should be required
reading for anybody who thinks it would be a fun and easy project to
break a commercial RSA key.
'On the Security of 1024-bit RSA and 160-bit Elliptic Curve
Cryptography' is a 2010-era update to the previous paper
Brian Murphy's thesis, 'Polynomial Selection for the Number Field
Sieve Algorithm', is simply awesome. It goes into excruciating
detail on a very undocumented subject.
Thorsten Kleinjung's 'On Polynomial Selection for the General Number
Field Sieve' explains in detail a number of improvements to
NFS polynomial selection developed since Murphy's thesis.
Kleinjung's latest algorithmic ideas on NFS polynomial selection
are documented at the 2008 CADO Factoring Workshop:
http://cado.gforge.inria.fr/workshop/abstracts.htmlJason Gower's 'Rotations and Translations of Number Field Sieve
Polynomials' describes some very promising improvements to the
polynomial generation process. As far as I know, nobody has actually
implemented them.
D.J. Bernstein has two papers in press and several slides on
some improvements to the polynomial selection process, that I'm
just dying to implement.
Aoki and Ueda's 'Sieving Using Bucket Sort' described the kind of
memory optimizations that a modern siever must have in order to
be fast
Dodson and Lenstra's 'NFS with Four Large Primes: An Explosive
Experiment' is the first realization that maybe people should
be using two large primes per side in NFS after all
Franke and Kleinjung's 'Continued Fractions and Lattice Sieving' is
the only modern reference available on techniques used in a high-
performance lattice siever.
Bob Silverman's 'Optimal Parametrization of SNFS' has lots of detail on
parameter selection and implementation details for building a line
siever
Ekkelkamp's 'On the amount of Sieving in Factorization Methods'
goes into a lot of detail on simulating NFS postprocessing
Cavallar's 'Strategies in Filtering in the Number Field Sieve'
is really the only documentation on NFS postprocessing
My talk 'A Self-Tuning Filtering Implementation for the Number
Field Sieve' describes research that went into Msieve's filtering code.
Denny and Muller's extended abstract 'On the Reduction of Composed
Relations from the Number Field Sieve' is an early attempt at NFS
filtering that's been almost forgotten by now, but their techniques
can work on top of ordinary NFS filtering
Montgomery's 'Square Roots of Products of Algebraic Numbers' describes
the standard algorithm for the NFS square root phase
Nguyen's 'A Montgomery-Like Square Root for the Number Field Sieve'
is also standard stuff for this subject; I haven't read this or the
previous paper in great detail, but that's because the convetional
NFS square root algorithm is still a complete mystery to me
David Yun's 'Algebraic Algorithms Using P-adic Constructions' provided
a lot of useful theoretical insight into the math underlying the
simplex brute-force NFS square root algorithm that msieve uses
Decio Luiz Gazzoni Filho adds:
The collection of papers `The Development of the Number Field
Sieve' (Springer Lecture Notes In Mathematics 1554) should be
absolutely required reading -- unfortunately it's very hard to get
ahold of. It's always marked `special order' at Amazon.com, and I
figured I shouldn't even try to order as they'd get back to me in a
couple of weeks saying the book wasn't available. I was very lucky to
find a copy available one day, which I promptly ordered. Again, I
cannot recommend this book enough; I had read lots of literature on
NFS but the first time I `got' it was after reading the papers here.
Modern expositions of NFS only show the algorithm as its currently
implemented, and at times certain things are far from obvious. Now
this book, being a historical account of NFS, shows how it progressed
starting from John Pollard's initial work on SNFS, and things that
looked out of place start to make sense. It's particularly
enlightening to understand the initial formulation of SNFS, without
the use of character columns.
[NOTE: this has been reprinted and is available from bn.com, at least -JP]
As usual, a very algebraic and deep exposition can be found in Henri
Cohen's book `A Course In Computational Algebraic Number Theory'.
Certainly not for the faint of heart though. It's quite dated as
well, e.g. the SNFS section is based on the `old' (without character
columns) SNFS, but explores a lot of the underlying algebra.
In order to comprehend NFS, lots of background on algebra and
algebraic number theory is necessary. I found a nice little
introductory book on algebraic number theory, `The Theory of
Algebraic Numbers' by Harry Pollard and Harold Diamond. It's an old
book, not contaminated by the excess of abstraction found on modern
books. It helped me a lot to get a grasp on the algebraic concepts.
Cohen's book is hard on the novice but surprisingly useful as one
advances on the subject, and the algorithmic touches certainly help.
As for papers: `Solving Sparse Linear Equations Over Finite Fields'
by Douglas Wiedemann presents an alternate method for the matrix
step. Block Lanczos is probably better, but perhaps Wiedemann's
method has some use, e.g. to develop an embarassingly parallel
algorithm for linear algebra (which, in my opinion, is the current
holy grail of NFS research).