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.html
Jason 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).