The LLL Algorithm Survey and Applications
- PDF / 6,490,030 Bytes
- 502 Pages / 439.37 x 666.142 pts Page_size
- 92 Downloads / 255 Views
Phong Q. Nguyen • Brigitte Vallée Editors
The LLL Algorithm Survey and Applications
123
Editors Dr. Phong Q. Nguyen INRIA Research Director École Normale Supérieure Département d'Informatique Paris, France [email protected]
ISSN 1619-7100 ISBN 978-3-642-02294-4 DOI 10.1007/978-3-642-02295-1
Dr. Brigitte Vallée CNRS Research Director and Ø Research Director Département d'Informatique Université de Caen, France [email protected]
e-ISBN 978-3-642-02295-1
Springer Heidelberg Dordrecht London New York Library of Congress Control Number: 2009934498 ACM Computing Classification (1998): F.2, F.1, E.3, G.1 © Springer-Verlag Berlin Heidelberg 2010 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specif ically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microf ilm 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. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specif ic statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: KuenkelLopka GmbH Printed on acid-free paper Springer is a part of Springer Science+Business Media (www.springer.com)
Preface
Computational aspects of geometry of numbers have been revolutionized by the Lenstra–Lenstra–Lov´asz lattice reduction algorithm (LLL), which has led to breakthroughs in fields as diverse as computer algebra, cryptology, and algorithmic number theory. After its publication in 1982, LLL was immediately recognized as one of the most important algorithmic achievements of the twentieth century, because of its broad applicability and apparent simplicity. Its popularity has kept growing since, as testified by the hundreds of citations of the original article, and the ever more frequent use of LLL as a synonym to lattice reduction. As an unfortunate consequence of the pervasiveness of the LLL algorithm, researchers studying and applying it belong to diverse scientific communities, and seldom meet. While discussing that particular issue with Damien Stehl´e at the 7th Algorithmic Number Theory Symposium (ANTS VII) held in Berlin in July 2006, John Cremona accurately remarked that 2007 would be the 25th anniversary of LLL and this deserved a meeting to celebrate that event. The year 2007 was also involved in another arithmetical story. In 2003 and 2005, Ali Akhavi, Fabien Laguillaumie, and Brigitte Vall´ee with other colleagues organized two workshops on cryptology and algorithms with a strong emphasis on lattice reduction: CAEN ’03 and CAEN ’05, CAEN denoting both the location and the con
Data Loading...
