Abstract
A modification, due to Peter Montgomery, of Pomerance’s Quadratic Sieve for factoring large integers is discussed along with its implementation. Using it, allows factorization with over an order of magnitude less sieving than the basic algorithm. It enables one to factor numbers in the 60-digit range in about a day, using a large minicomputer. The algorithm has features which make it well adapted to parallel implementation.
Keywords
MathematicsQuadratic equationFactorizationSieve (category theory)PolynomialFactoringRange (aeronautics)Factorization of polynomialsDiscrete mathematicsCombinatoricsAlgorithmMatrix polynomialMathematical analysis
Related Publications
Faster factoring of integers of a special form
. A speedup of Lenstra's Elliptic Curve Method of factorization is presented. The speedup works for integers of the form N = PQ^2 , where P is a prime sufficiently smal...
New algorithms for finding irreducible polynomials over finite fields
We present a new algorithm for finding an irreducible polynomial of specified degree over a finite field. Our algorithm is deterministic, and it runs in polynomial time for fiel...
Efficient networks for quantum factoring
We consider how to optimize memory use and computation time in operating a quantum computer. In particular, we estimate the number of memory quantum bits (qubits) and the number...
SOME PUBLIC-KEY CRYPTO-FUNCTIONS AS INTRACTABLE AS FACTORIZATION
In the RSA public-key crypto system a message M (<R) is encrypted by calculating K≡me (mod R), where 0<K<R and R, e are integers which are made public. The recipient of K can de...
Publication Info
- Year
- 1987
- Type
- article
- Volume
- 48
- Issue
- 177
- Pages
- 329-339
- Citations
- 150
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
150
OpenAlex
Cite This
Robert Silverman
(1987).
The multiple polynomial quadratic sieve.
Mathematics of Computation
, 48
(177)
, 329-339.
https://doi.org/10.1090/s0025-5718-1987-0866119-8
Identifiers
- DOI
- 10.1090/s0025-5718-1987-0866119-8