Factoring with two large primes

Lenstra, A. K.; Manasse, M. S.

doi:10.1090/S0025-5718-1994-1250773-9

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

Solving large sparse systems over finite fields

Massively parallel computing and factoring

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

Factoring with two large primes

K. Mehlhorn and A. Tsakalidis, Data structures, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 301–341. MR 1127172

A short note on analyzing the large prime variation

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
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