Quantum Computational Number Theory
This book provides a comprehensive introduction to advanced topics in the computational and algorithmic aspects of number theory, focusing on applications in cryptography. Readers will learn to develop fast algorithms, including quantum algorithms, to sol
- PDF / 2,931,433 Bytes
- 259 Pages / 439.42 x 683.15 pts Page_size
- 35 Downloads / 233 Views
Quantum Computational Number Theory
Quantum Computational Number Theory
Song Y. Yan
Quantum Computational Number Theory
123
Song Y. Yan Wuhan University Wuhan, China
ISBN 978-3-319-25821-8 ISBN 978-3-319-25823-2 (eBook) DOI 10.1007/978-3-319-25823-2 Library of Congress Control Number: 2015953668 Springer Cham Heidelberg New York Dordrecht London © Springer International Publishing Switzerland 2015 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. Printed on acid-free paper Springer International Publishing AG Switzerland is part of Springer Science+Business Media (www. springer.com)
Preface
Imagination is more important than knowledge. Knowledge is limited. Imagination encircles the world. ALBERT EINSTEIN (1879–1955) The 1921 Nobel Laureate in Physics
Quantum computational number theory is a new interdisciplinary subject of number theory, computation theory, and quantum computing together. The aim of quantum computational number theory is to use the new quantum computing techniques to solve the intractable computational problems in number theory and numbertheoretic cryptography. Indeed, the most famous quantum algorithm, namely, Shor’s quantum factoring algorithm, is for solving the integer factorization problem and for breaking the RSA cryptographic system. The book consists of six chapters. In Chapter 1, we try to answer briefly what is computational number theory and what is quantum computational number theory. Chapter 2 presents some basic concepts and results in classical and quantum computation. Chapter 3 gives an account of classical and quantum algorithms for the integer factorization problem (IFP). Chapter 4 discusses classical and quantum algorithms for the discrete logarithm problems (DLP), whereas Chapter 5 deals with classical and quantum algorithms for elliptic curve discrete logarithm problems (ECDLP). Since all classical algorithms are not powerful enough to solve IFP, DLP, and ECDLP in polynomial-time, all IFP-, DLP-, and ECDLP-based cryptographic s
Data Loading...
