Subexponential Factoring Algorithms

Richard Crandall () and Carl Pomerance ()
Additional contact information
Richard Crandall: Center for Advanced Computation
Carl Pomerance: Dartmouth University, Department of Mathematics

Chapter Chapter 6 in Prime Numbers, 2001, pp 227-283 from Springer

Abstract: Abstract The methods of this chapter include two of the three basic workhorses of modern factoring, the quadratic sieve (QS) and the number field sieve (NFS). (The third workhorse, the elliptic curve method (ECM), is described in Chapter 7.) The quadratic sieve and number field sieve are direct descendants of the continued fraction factoring method of Brillhart and Morrison, which was the first subexponential factoring algorithm on the scene. The continued fraction factoring method, which was introduced in the early 1970s, allowed complete factorizations of numbers of around 50 digits, when previously, about 20 digits had been the limit. The quadratic sieve and the number field sieve, each with its strengths and domain of excellence, have pushed our capability for complete factorization from 50 digits to now over 150 digits for the size of numbers to be routinely factored. By contrast, the elliptic curve method has allowed the discovery of prime factors up to 50 digits and beyond, with fortunately weak dependence on the size of number to be factored. We include in this chapter a small discussion of rigorous factorization methods that in their own way also represent the state of the art. We also discuss briefly some subexponential discrete logarithm algorithms for the multiplicative groups of finite fields.

Keywords: Prime Ideal; Algebraic Integer; Free Relation; Gaussian Integer; Nontrivial Factorization (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4684-9316-0_6

Ordering information: This item can be ordered from
http://www.springer.com/9781468493160

DOI: 10.1007/978-1-4684-9316-0_6

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().