Abstract
The study of integer factoring algorithms and the design of faster factoring algorithms is a subject of great importance in cryptology (cf. [1]), and a constant concern for cryptographers. In this paper we present a new technique that proved to be extremely useful, not only to achieve a considerable speed-up of an older and widely studied factoring algorithm, but also, and more importantly, to make practical application of a new factoring algorithm feasible. While this first application does not pose serious threats to factorization-based cryptosystems, the consequences of the second application could be very encouraging (from the cryptanalysts point of view).
Chapter PDF
Similar content being viewed by others
References
G. Brassard, Modern Cryptology, Lecture Notes in Computer Science, vol. 325, 1988, Springer-Verlag.
J. Brillhart, D.H. Lehmer, J.L. Selfridge, B. Tuckerman, S.S. Wagstaff, Jr., Factorizations of b n±1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers, second edition, Contemporary Mathematics, vol. 22, Amer. Math. Soc., Providence, Rhode Island 1988.
W. Bosma, M.-P. van der Hulst, A.K. Lenstra, “An improved version of the Jacobi sum primality test,” in preparation.
J. Buhler, H.W. Lenstra, Jr., C. Pomerance, in preparation.
H. Cohen, A.K. Lenstra, “Implementation of a new primality test,” Math. Comp., v. 48, 1987, pp. 103–121.
A.K. Lenstra, H.W. Lenstra, Jr., “Algorithms in number theory,” in: J. van Leeuwen, A. Meyer, M. Nivat, M. Paterson, D. Perrin (eds), Handbook of theoretical computer science, to appear.
A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard, “The number field sieve,” to appear.
A.K. Lenstra, M.S. Manasse, “Factoring by electronic mail,” Proceedings Eurocrypt’ 89.
H. W. Lenstra, Jr., personal communication.
F. Morain, “Primality testing: News from the front,” Proceedings Eurocrypt’ 89.
C. Pomerance, “Analysis and comparison of some integer factoring algorithms,” pp. 89–139 in: H.W. Lenstra, Jr., R. Tijdeman (eds), Computational methods in number theory, Mathematical Centre Tracts 154, 155, Mathematisch Centrum, Amsterdam, 1982.
R. D. Silverman, “The multiple polynomial quadratic sieve,” Math. Comp., v. 48, 1987, pp. 329–339.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lenstra, A.K., Manasse, M.S. (1991). Factoring with two large primes. In: Damgård, I.B. (eds) Advances in Cryptology — EUROCRYPT ’90. EUROCRYPT 1990. Lecture Notes in Computer Science, vol 473. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46877-3_7
Download citation
DOI: https://doi.org/10.1007/3-540-46877-3_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53587-4
Online ISBN: 978-3-540-46877-6
eBook Packages: Springer Book Archive