The Development of the Number Field Sieve (Google eBook)
Arjen K. Lenstra, Hendrik W.Jr. Lenstra
Springer Science & Business Media, Aug 30, 1993 - Mathematics - 131 pages
The number field sieve is an algorithm for finding the prime factors of large integers. It depends on algebraic number theory. Proposed by John Pollard in 1988, the method was used in 1990 to factor the ninth Fermat number, a 155-digit integer. The algorithm is most suited to numbers of a special form, but there is a promising variant that applies in general. This volume contains six research papers that describe the operation of the number field sieve, from both theoretical and practical perspectives. Pollard's original manuscript is included. In addition, there is an annotated bibliography of directly related literature.
What people are saying - Write a review
We haven't found any reviews in the usual places.
abra algebraic integer algebraic number fields algebraic number theory analysis arithmetic asymptotically bound choice choose coefficients complexity compute coordinates coprime coprime integers corresponding cycles defined degree prime ideals denote described digits discrete logarithm divide elements elliptic curve method equal Equations factor base factoring algorithms Factoring integers factorisation finite field GNFS H. W. Lenstra heuristic homomorphism ideals of norm implementation irreducible J.M. Pollard lattice sieve linear Manasse MasPar Math matrix mod q modp modulo multiple ninth Fermat number non-trivial factor non-zero number field sieve number q pairs parameters partial relations polynomial f Pomerance positive integer prime factor prime ideals prime number primes q problem Proceedings processor quadratic characters quadratic sieve Remark ring of integers rows satisfies Section smooth square root Step theorem trial division unique factorization domain units values vectors y-smooth Z/nZ