Lawrence C. Washington - Elliptic Curves: Number Theory and Cryptography

Cover

Page i

Series Editor

Kenneth H.Rosen, Ph.D.

AT&T Laboratories
Middletown, New Jersey

Applications of Abstract Algebra with Maple,
Richard E.Klima, Ernest Stitzinger, and Neil P.Sigmon

Algebraic Number Theory, Richard A.Mollin

An Atlas of Smaller Maps in Orientable and Nonorientable Surfaces,
David M.Jackson and Terry I.Visentin

An Introduction to Crytography, Richard A.Mollin

Combinatorial Algorithms: Generation Enumeration and Search,
Donald L.Kreher and Douglas R.Stinson

The CRC Handbook of Combinatorial Designs,
Charles J.Colbourn and Jeffrey H.Dinitz

Cryptography: Theory and Practice, Second Edition, Douglas R.Stinson

Design Theory, Charles C.Lindner and Christopher A.Rodgers

Enumerative Combinatorics,
Charalambos A.Charalambides

Frames and Resolvable Designs: Uses, Constructions, and Existence,
Steven Furino, Ying Miao, and Jianxing Yin

Fundamental Number Theory with Applications, Richard A.Mollin

Graph Theory and Its Applications, Jonathan Gross and Jay Yellen

Handbook of Applied Cryptography,
Alfred J.Menezes, Paul C.van Oorschot, and Scott A.Vanstone

Handbook of Discrete and Combinatorial Mathematics, Kenneth H.Rosen

Handbook of Discrete and Computational Geometry,
Jacob E.Goodman and Joseph ORourke

Introduction to Information Theory and Data Compression, Second Edition,
Darrel R.Hankerson, Greg A.Harris, and Peter D.Johnson

Page ii

Continued Titles

Network Reliability: Experiments with a Symbolic Algebra Environment,
Daryl D.Harms, Miroslav Kraetzl, Charles J.Colbourn, and John S.Devitt

RSA and Public-Key Cryptography
Richard A.Mollin

Quadratics, Richard A.Mollin

Verification of Computer Codes in Computational Science and Engineering,
Patrick Knupp and Kambiz Salari

Elliptic Curves: Number Theory and Cryptography
Lawrence C.Washington

Page iii

DISCRETE MATHEMATICS AND ITS APPLICATIONS
Series Editor KENNETH H.ROSEN

Number Theory and Cryptography

Lawrence C.Washington

CHAPMAN & HALL/CRC

A CRC Press Company

Boca Raton London NewYork Washington, D.C.

Page iv

This edition published in the Taylor & Francis e-Library, 2005.

To purchase your own copy of this or any of Taylor & Francis or Routledges collection of thousands of eBooks please go to www.eBookstore.tandf.co.uk.

Library of Congress Cataloging-in-Publication Data

Washington, Lawrence C.
Elliptic curves: number theory and cryptography/Lawrence C.Washington.
p. cm.(Discrete mathematics and its applications)
Includes bibliographical references and index.
ISBN 1-58488-365-0 (alk. paper)
1. Curves, Elliptic. 2. Number theory. 3. Cryptography. I. Title. II. CRC Press Press series on
discrete mathematics and its applications.

QA567.2.E44W37 2003
516.352dc21 2003043972

This book contains information obtained from authentic and highly regarded sources. Reprinted material
is quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable
efforts have been made to publish reliable data and information, but the author and the publisher cannot
assume responsibility for the validity of all materials or for the consequences of their use.

Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic
or mechanical, including photocopying, microfilming, and recording, or by any information storage or
retrieval system, without prior permission in writing from the publisher.

The consent of CRC Press LLC does not extend to copying for general distribution, for promotion, for
creating new works, or for resale. Specific permission must be obtained in writing from CRC Press LLC
for such copying.

Direct all inquiries to CRC Press LLC, 2000 N.W. Corporate Blvd., Boca Raton, Florida 33431.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are
used only for identification and explanation, without intent to infringe.

Visit the CRC Press Web site atwww.crcpress.com

2003 by Chapman & Hall/CRC

No claim to original U.S. Government works

ISBN 0-203-48402-9 Master e-book ISBN

ISBN 0-203-62068-2 (OEB Format)

International Standard Book Number 1-58488-365-0 (Print Edition)

Library of Congress Card Number 2003043972

Page v

Over the last two or three decades, elliptic curves have been playing an increasingly important role both in number theory and in related fields such as cryptography. For example, in the 1980s, elliptic curves started being used in cryptography and elliptic curve techniques were developed for factorization and primality testing. In the 1980s and 1990s, elliptic curves played an important role in the proof of Fermats Last Theorem. The goal of the present book is to develop the theory of elliptic curves assuming only modest backgrounds in elementary number theory and in groups and fields, approximately what would be covered in a strong undergraduate or beginning graduate abstract algebra course. In particular, we do not assume the reader has seen any algebraic geometry. Except for a few isolated sections, which can be omitted if desired, we do not assume the reader knows Galois theory. We implicitly use Galois theory for finite fields, but in this case everything can be done explicitly in terms of the Frobenius map so the general theory is not needed. The relevant facts are explained in an appendix.

The book provides an introduction to both the cryptographic side and the number theoretic side of elliptic curves. For this reason, we treat elliptic curves over finite fields early in the book, namely in Chapter 4. This immediately leads into the discrete logarithm problem and cryptography in Chapters 5, 6, and 7. The reader only interested in cryptography can subsequently skip to Chapters 10 and 11, where complex multiplication and the Weil and Tate-Lichtenbaum pairings are discussed. But surely anyone who becomes an expert in cryptographic applications will have a little curiosity as to how elliptic curves are used in number theory. Similarly, a non-applications oriented reader could skip Chapters 5, 6, and 7 and jump straight into the number theory in Chapters 8 and beyond. But the cryptographic applications are interesting and provide examples for how the theory can be used.