## Factoring with two large primes

HTML articles powered by AMS MathViewer

- by A. K. Lenstra and M. S. Manasse PDF
- Math. Comp.
**63**(1994), 785-798 Request permission

## Abstract:

We describe a modification to the well-known large prime variant of the multiple polynomial quadratic sieve factoring algorithm. In practice this leads to a speed-up factor of 2 to 2.5. We discuss several implementation-related aspects, and we include some examples. Our new variation is also of practical importance for the number field sieve factoring algorithm.## References

- Daniel J. Bernstein and A. K. Lenstra,
*A general number field sieve implementation*, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 103–126. MR**1321223**, DOI 10.1007/BFb0091541 - John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr.,
*Factorizations of $b^n \pm 1$*, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. $b=2,3,5,6,7,10,11,12$ up to high powers. MR**996414**, DOI 10.1090/conm/022 - J. D. Horton,
*A polynomial-time algorithm to find the shortest cycle basis of a graph*, SIAM J. Comput.**16**(1987), no. 2, 358–366. MR**882536**, DOI 10.1137/0216026
B. A. LaMacchia and A. M. Odlyzko, - A. K. Lenstra and H. W. Lenstra Jr.,
*Algorithms in number theory*, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 673–715. MR**1127178** - A. K. Lenstra and H. W. Lenstra Jr. (eds.),
*The development of the number field sieve*, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR**1321216**, DOI 10.1007/BFb0091534 - A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse, and J. M. Pollard,
*The number field sieve*, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 11–42. MR**1321219**, DOI 10.1007/BFb0091537 - A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse, and J. M. Pollard,
*The factorization of the ninth Fermat number*, Math. Comp.**61**(1993), no. 203, 319–349. MR**1182953**, DOI 10.1090/S0025-5718-1993-1182953-4 - Arjen K. Lenstra and Mark S. Manasse,
*Factoring by electronic mail*, Advances in cryptology—EUROCRYPT ’89 (Houthalen, 1989) Lecture Notes in Comput. Sci., vol. 434, Springer, Berlin, 1990, pp. 355–371. MR**1083962**, DOI 10.1007/3-540-46885-4_{3}5
—, - K. Mehlhorn and A. Tsakalidis,
*Data structures*, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 301–341. MR**1127172**
F. Morain, - Keith Paton,
*An algorithm for the blocks and cutnodes of a graph*, Comm. ACM**14**(1971), 468–475. MR**0306007**, DOI 10.1145/362619.362628 - C. Pomerance,
*Analysis and comparison of some integer factoring algorithms*, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR**700260** - Carl Pomerance and J. W. Smith,
*Reduction of huge, sparse matrices over finite fields via created catastrophes*, Experiment. Math.**1**(1992), no. 2, 89–94. MR**1203868**
R. D. Silverman, private communication.
- Jan van Leeuwen (ed.),
*Handbook of theoretical computer science. Vol. A*, Elsevier Science Publishers, B.V., Amsterdam; MIT Press, Cambridge, MA, 1990. Algorithms and complexity. MR**1127166** - J. van Leeuwen,
*Graph algorithms*, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 525–631. MR**1127176**
S. S. Wagstaff, Jr., Update 2.4 to [2].

*Solving large sparse systems over finite fields*, Advances in Cryptology, Proc. Crypto ’90, Lecture Notes in Comput. Sci., vol. 537, Springer-Verlag, Berlin and New York, 1991, pp. 109-133. A. K. Lenstra,

*Massively parallel computing and factoring*, Proc. Latin ’92, Lecture Notes in Comput. Sci., vol. 583, Springer-Verlag, Berlin and New York, 1992, pp. 344-355.

*Factoring with two large primes*, Advances in Cryptology, Eurocrypt ’90, Lecture Notes in Comput. Sci., vol. 473, Springer-Verlag, Berlin and New York, 1991, pp. 72-82.

*A short note on analyzing the large prime variation*, manuscript, 1991.

## Additional Information

- © Copyright 1994 American Mathematical Society
- Journal: Math. Comp.
**63**(1994), 785-798 - MSC: Primary 11Y05
- DOI: https://doi.org/10.1090/S0025-5718-1994-1250773-9
- MathSciNet review: 1250773