Yan - Computational Number Theory and Modern Cryptography

INFORMATION SECURITY SERIES

The Wiley-HEP Information Security Series systematically introduces the fundamentals of information security design and application. The goals of the Series are:

• to provide fundamental and emerging theories and techniques to stimulate more research in cryptology, algorithms, protocols, and architectures
• to inspire professionals to understand the issues behind important security problems and the ideas behind the solutions
• to give references and suggestions for additional reading and further study

The Series is a joint project between Wiley and Higher Education Press (HEP) of China. Publications consist of advanced textbooks for graduate students as well as researcher and practitioner references covering the key areas, including but not limited to:

LEAD EDITORS

EDITORIAL BOARD

This edition first published 2013
2013 Higher Education Press. All rights reserved.

Published by John Wiley & Sons Singapore Pte. Ltd., 1 Fusionopolis Walk, #07-01 Solaris South Tower, Singapore 138628, under exclusive license by Higher Education Press in all media and all languages throughout the world excluding Mainland China and excluding Simplified and Traditional Chinese languages.

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com .

All Rights Reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as expressly permitted by law, without either the prior written permission of the Publisher, or authorization through payment of the appropriate photocopy fee to the Copyright Clearance Center. Requests for permission should be addressed to the Publisher, John Wiley & Sons Singapore Pte. Ltd., 1 Fusionopolis Walk, #07-01 Solaris South Tower, Singapore 138628, tel: 65-66438000, fax: 65-66438008, email: enquiry@wiley.com.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The Publisher is not associated with any product or vendor mentioned in this book. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold on the understanding that the Publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

Library of Congress Cataloging-in-Publication Data

Yan, Song Y.

Computational number theory and modern cryptography / Song Y. Yan.
pages cm
Includes bibliographical references and index.
ISBN 978-1-118-18858-3 (hardback)
1. Data encryption (Computer science) 2. Number theoryData processing. I. Title.
QA76.9.A25Y358 2012
005.82dc23

2012032708

ISBN: 9781118188583

ABOUT THE AUTHOR

Professor Song Y. Yan majored in both Computer Science and Mathematics, and obtained a PhD in Number Theory in the Department of Mathematics at the University of York, England. His current research interests include Computational Number Theory, Computational Complexity Theory, Algebraic Coding Theory, Public-Key Cryptography and Information/Network Security. He published, among others, the following five well-received and popular books in computational number theory and public-key cryptography:

Song can be reached by email address songyuanyan@gmail.com anytime.

PREFACE

The book is about number theory and modern cryptography. More specically, it is about computational number theory and modern public-key cryptography based on number theory. It consists of four parts. The first part, consisting of two chapters, provides some preliminaries. Chapter 1 provides some basic concepts of number theory, computation theory, computational number theory, and modern public-key cryptography based on number theory. In chapter 2, a complete introduction to some basic concepts and results in abstract algebra and elementary number theory is given.

The second part is on computational number theory. There are three chapters in this part. Chapter 3 deals with algorithms for primality testing, with an emphasis on the Miller-Rabin test, the elliptic curve test, and the AKS test. Chapter 4 treats with algorithms for integer factorization, including the currently fastest factoring algorithm NFS (Number Field Sieve), and the elliptic curve factoring algorithm ECM (Elliptic Curve Method). Chapter 5 discusses various modern algorithms for discrete logarithms and for elliptic curve discrete logarithms. It is well-known now that primality testing can be done in polynomial-time on a digital computer, however, integer factorization and discrete logarithms still cannot be performed in polynomial-time. From a computational complexity point of view, primality testing is feasible (tractable, easy) on a digital computer, whereas integer factorization and discrete logarithms are infeasible (intractable, hard, difficult). Of course, no-one has yet been able to prove that the integer factorization and the discrete logarithm problems must be infeasible on a digital computer.