The development of the number field sieve
The number field sieve is an algorithm for finding the prime factors of large integers. It depends on algebraic number theory. Proposed by John Pollard in 1988, the method was used in 1990 to factor the ninth Fermat number, a 155-digit integer. The algori
- PDF / 12,516,888 Bytes
- 138 Pages / 468 x 684 pts Page_size
- 116 Downloads / 504 Views
1554
A. K. Lenstra H. W Lenstra, Jr.
(Eds.)
The development of the number field • SIeve
Springer-Verlag Berlin Heidelberg NewYork London Paris Tokyo Hong Kong Barcelona Budapest
Editors Arjen K. Lenstra Room MRE-2Q334 Bellcore 445 South Street Morristown, NJ 07960, USA E-mail: [email protected]
Hendrik W. Lenstra, Jr. Department of Mathematics University of California Berkeley, CA 94720, USA E-mail: [email protected]
Mathematics Subject Classification (1991): 11Y05, 11 Y40 ISBN 3-540-57013-6 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-57013-6 Springer-Verlag New York Berlin Heidelberg This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law.
© Springer-Verlag Berlin Heidelberg 1993 Printed in Germany 46/3140-543210 - Printed on acid-free paper
PREFACE The number field sieve is an algorithm for factoring integers that John Pollard proposed in 1988. This volume contains six papers on the number field sieve. They are preceded by an annotated bibliography, to which we refer for a brief description of the contents of each individual paper. We assume the reader to be familiar with the basic techniques that underlie modern integer factoring methods. An introduction to these techniques is given Ill:
A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard, The factorization of the ninth Fermat number, Math. Compo 61 (1993), to appear. The same paper includes a discussion of tools from algebraic number theory that the number field sieve depends on. Comprehensive accounts of older algorithms for factoring integers and related problems, with extensive bibliographies, can be found in: A. K. Lenstra, H. W. Lenstra, Jr., Algorithms in number theory, Chapter 12 in: J. van Leeuwen (ed.), Handbook of theoretical computer science, Volume A, Algorithms and complexity, Elsevier, Amsterdam, 1990, C. Pomerance (ed.), Cryptology and computational number theory, Proc. Sympos. Appl. Math. 42, Amer. Math. Soc., Providence, 1990. The developments leading up to the number field sieve are sketched on pp. 1113 below. The annotated bibliography (pp. 13) tells, implicitly, the recent history of the number field sieve itself. We express our gratitude to the authors of the papers for contributing their work to this volume. In particular we wish to thank Carl Pomerance for conceiving the idea of a combined publication and for advising us in all stages of its execution. In addition, we thank Henri Cohen, Dan Gordon, Andrew Odlyzko, Jonathan Pila, and Tom Trotter for their assistance. W
Data Loading...
