Yan S. Y. - Number Theory For Computing.pdf - Number Theory - annam101

Song Y. Yan

Number Theory

for Computin g

Second Edition

Foreword by Martin E. Hellman

With 26 Figures, 78 Images, and 33 Table s

Springer

Berli n

Heidelberg

New York

Barcelon a

Hong Kon g

Londo n

Mila n

Pari s

Tokyo

Springer

Song Y . Ya n

Computer Science

Aston Universit y

Birmingham B4 7E T

U K

s .yan@aston .ac .uk

Foreword

ACM Computing Classification (1998) : F.2 .1, E .3-4, D .4 .6, B .2 .4, 11 . 2

AMS Mathematics Subject Classification (1991) : 1 lAxx, 1 IT71 ,

11Yxx, 11Dxx, 11Z05, 68Q25, 94A6 0

Modern cryptography depends heavily on number theory, with primality test-

ing, factoring, discrete logarithms (indices), and elliptic curves being perhap s

the most prominent subject . areas . Since my own graduate study had empha-

sized probability theory, statistics, and real analysis, when I started work-

ing in cryptography around 1970, I found myself swimming in an unknown ,

murky sea . I thus know from personal experience how inaccessible numbe r

theory can be to the uninitiated . Thank you for your efforts to ease th e

transition for a new generation of cryptographers .

Library of Congress Cataloging-in-Publication Data applied fo r

Die Deutsche Bibliothek - CIP-Einheitsaufnahm e

Yan, Song Y. :

Number theory for computing : with 32 tables/Song Y. Yan . - 2. ed ., rev.

and extended. - Berlin; Heidelberg ; New York; Barcelona ; Hong Kong ;

London; Milan ; Paris ; Tokyo : Springer, 200 2

ISBN 3-540-43072- 5

Thank you also for helping Ralph Merkle receive the credit he deserves .

Diffie, Rix-est . Shamir . Adleman and I had the good luck to get expedite d

review of our papers, so that they appeared before Merkle's seminal contribu-

tion . Your noting his early submission date and referring to what has come t o

be called "Diffie-Hellman key exchange" as it should, "Diffie-Hellman-Merkl e

key exchange", is greatly appreciated .

ISBN 3-540-43072-5 Springer-Verlag Berlin Heidelber New Yor k

ISBN 3-540-65472-0 Springer-Verlag Berlin Heidelberg New York (1st ed . )

It has been gratifying to see how cryptography and number theory hav e

helped each other over the last twenty-five years . Number theory has bee n

the source of numerous clever ideas for implementing cryptographic system s

and protocols while cryptography has been helpful in getting funding for this

area which has sometimes been called the queen of mathematics" becaus e

of its seeming lack of real world applications . Little did they know !

This work is subject to copyright . All rights are reserved, whether the whole or part of th e

material is concerned, specifically the rights of translation, reprinting, reuse of illustrations ,

recitation, broadcasting, reproduction on microfilm or in any other way, and storage in dat a

banks . Duplication of this publication or parts thereof is permitted only under th e

provisions of the German Copyright Law of September 9, 1965, in its current version, an d

permission for use must always be obtained from Springer-Verlag . Violations are liable fo r

prosecution under the German Copyright Law .

Springer-Verlag Berlin Heidelberg New York ,

a member of BertelsmannSpringer Science+Business Media Gmb H

http ://www.springende

Springer-Verlag Berlin Heidelberg 2000, 200 2

Printed in German y

The use of general descriptive names, trademarks, etc . in this publication does not imply ,

even in the absence of a specific statement, that such names are exempt from the relevan t

protective laws and regulations and therefore free for general use .

Cover Design : KunkelLopka, Heidelber g

Typesetting : Camera ready by the author

Printed on acid-free paper

Stanford, 30 .July 2001

Martin E . Hellman

SPIN 10852441

45/3142SR - 5 4 3 2 1 0

Preface to the Second Editio n

Number theory is an experimental science

J . W . S . CASSELS (1922 -

Professor Emeritus of Mathematics . The University of Cambridg e

If you teach a course on number theory nowadays, chances are it will gen-

erate more interest among computer science majors than among mathe-

matics majors . Many will care little about integers that can be expresse d

as the sum of two squares . They will prefer to learn how Alice can send a

message to Bob without fear of eavesdropper Eve deciphering it .

BRAIN E . BLANK, Professor of Mathematic s

Washington University. St. . Louis, Missouri

The success of the first edition of the book encouraged me to produce thi s

second edition . I have taken this opportunity to provide proofs of many the-

orems, that had not been given in the first edition . Some additions and cor-

rections have also been included .

Since the publication of the first edition . I have received many communica-

tions from readers all over the world . It is my great pleasure to thank the fol-

lowing people for their comments . corrections and encouragements : Prof . Ji m

Austin, Prof . Friedrich L . Bauer . Dr . Hassan Daghigh Dr . Deniz Deveci .

Mr . Rich Fearn, Prof . Martin Hellman . Prof. Zixin Hou . Mr . Waseem Hus-

sain, Dr . Gerard R . Maze . Dr . Paul Maguire . Dr . Helmut Mevn . Mr . Rober t

Pargeter . Mr . Mok-Kong Shen . Dr . Peter Shiu . Prof . Jonathan P . Sorenson .

and Dr . David L . Stern . Special thanks must be given to Prof. Martin Hell-

man of Stanford University for writing the kind Foreword to this edition and

also for his helpful advice and kind guidance . to Dr . Hans Wossner . Mr . Al-

fred Hofmann, Mrs . Ingeborg Mayer, Mrs . Ulrike Stricken, and Mr . Frank

Holzwarth of Springer-Verlag for their kind help and encouragements dur-

ing the preparation of this edition, and to Dr . Rodney Coleman . Prof. Gly n

James, Mr . Alexandros Papanikolaou . and Mr . Robert Pargeter for proof-

reading the final draft . Finally. I would like to thank Prof . Shiing-Shen Chern .

Preface to the Second Editio n

Director Emeritus of the Mathematical Sciences Research Institute in Berke -

ley for his kind encouragements ; this edition is dedicated to his 90th birthday !

Preface to the First Editio n

Readers of the book are, of course, very welcome to communicate wit h

the author either by ordinary mail or by e-mail to s . yan@aston . ac . uk, s o

that your corrections, comments and suggestions can be incorporated into a

future edition .

Birmingham . February 2002

S . Y . Y .

Mathematicians do not study objects, but relations among objects ; they ar e

indifferent to the replacement of objects by others as long as relations d o

not change . Matter is not important, only form interests them .

HENRI PoINCARr (1854-1912 )

Computer scientists working on algorithms for factorization would be wel l

advised to brush up on their number theory .

IAN STEWART

Geometry Finds Factor Fast

Nature, Vol . 325, 15 January 1987, page 199

The theory of numbers, in mathematics, is primarily the theory of the prop-

erties of integers (i .e ., the whole numbers), particularly the positive integers .

For example, Euclid proved 2000 years ago in his Elements that there ex-

ist infinitely many prime numbers . The subject had long been considered a s

the purest branch of mathematics, with very few applications to other ar-

eas . However, recent years have seen considerable increase in interest in sev-

eral central topics of number theory, precisely because of their importanc e

and applications in other areas, particularly in computing and informatio n

technology. Today, number theory has been applied to such diverse areas a s

physics, chemistry, acoustics, biology, computing, coding and cryptography,

digital communications, graphics design, and even music and business' . In

particular, congruence theory has been used in constructing perpetual calen-

dars, scheduling round-robin tournaments, splicing telephone cables, devisin g

systematic methods for storing computer files, constructing magic squares ,

generating random numbers, producing highly secure and reliable encryptio n

schemes and even designing high-speed (residue) computers . It is specificall y

worthwhile pointing out that computers are basically finite machines ; the y

1 In his paper [96] in the International Business Week, 20 June 1994, pp . 62-64 ,

Fred Guterl wrote : " Number Theory, once the esoteric study of what happen s

when whole numbers are manipulated in various ways, is becoming a vital prac -

tical science that is helping solve tough business problems " .

Preface to the First Edition

have finite storage . can only deal with numbers of some finite length and ca n

only perform essentially finite steps of computation . Because of such limita-

tions . congruence arithmetic is particularly useful in computer hardware an d

software design .

This book takes the reader on a journey, starting at elementary numbe r

theory . going through algorithmic and computational number theory . an d

finally finishing at applied number theory in computing science . It is divide d

into three distinct parts :

methods . A small number of exercises is also provided in some sections . an d

it is worthwhile trying all of them .

The book is intended to be self-contained with no previous knowledg e

of number theory and abstract algebra assumed . although some familiarity

with first, year undergraduate mathematics will be helpful . The book is suit -

able either as a text for an undergraduate/postgraduate course in Numbe r

Theory/Mathematics for Computing/Cryptography . or as a basic referenc e

researchers in the field .

(1) Elementary Number Theory ,

(2) Computational/Algorithmic Number Theory ,

(3) Applied Number Theory in Computing and Cryptography .

Acknowledgement s

The first part is mainly concerned with the basic concepts and results of divis-

ibility theory, congruence theory, continued fractions . Diophantine equation s

and elliptic curves . A novel feature of this part is that it contains an ac -

count of elliptic curves . which is not normally provided by an elementar y

number theory book . The second part provides a brief introduction to th e

basic concepts of algorithms and complexity, and introduces some importan t

and widely used algorithms in computational number theory . particularl y

those for prirnality testing, integer factorization . discrete logarithms, and el-

liptic curve discrete logarithms . An important feature of this part is tha t

it contains a section on quantum algorithms for integer factorization an d

discrete logarithms, which cannot be easily found, so far, in other texts o n

computational/algorithmic number theory . This part finishes with section s

on algorithms for computing x( :r .), for finding amicable pairs, for verifyin g

Goldbach's conjecture, and for finding perfect and amicable numbers . Th e

third part of the book discusses some novel applications of elementary an d

computational number theory in computing and information technology, par-

ticularly in cryptography and information security ; it covers a wide range o f

topics such as secure communications, information systems security . com-

puter organisations and design . error detections and corrections . hash func-

tion design . and random number generation . Throughout the book we follo w

the style "Definition-Theorem-Algorithm-Example " to present our material ,

rather than the traditional Hardy Wright "Definition-Theorem-P1oof " styl e

[100], although we do give proofs to most of the theorems . We believe this is

the most . suitable way to present mathematical material to computing profes-

sionals . As Donald Knuth [121] pointed out in 1974 : "It has often been sai d

that a. person does not really understand something until he teaches it t o

someone else . Actually a person does not really understand something unti l

he can teach it to a computer . The author strongly recommends reader s

to implement all the algorithms and methods introduced in this book on a

computer using a . mathematics (computer algebra) system such as Maple i n

order to get a better understanding of the ideas behind the algorithms and

I started to write this book in 1990 when I was a lecturer in the School of

Mathematical and Information Sciences at La Trobe University . Australia .

I completed the book when I was at the University of York and finalized i t

at Coventry and Aston Universities . all in England . I am very grateful t o

Prof. Bertram Mond and Dr . John Zeleznikow of the School of Mathemat-

ical and Information Sciences at La . Trobe University . Dr . Terence Jackson

of the Department of Mathematics and Prof . Jim Austin of the Departmen t

of Computer Science at the University of York, Prof. Glyn James . Mr . Brian

Aspinall and Mr . Eric Tatham of the School of Mathematical and Informa-

tion Sciences at Coventry University, and Prof . David Lowe and Dr . Ted

Elsworth of Computer Science and Applied Mathematics at Aston Univer-

sity in Birmingham for their many fruitful discussions . kind encouragement

and generous support . Special thanks must be given to Dr . Hans Wossner

and Mr . Andrew Ross at Springer-Verlag Berlin/Heidelberg and the referees

of Springer-Verlag, for their comments, corrections and suggestions . Durin g

the long period of the preparation of the book . I also got much help in on e

way or another from, whether they are aware of it, or not, Prof. Eric Bach of

the University of Wisconsin at Madison . Prof. Jim Davenport of the Univer-

sity of Bath . Prof . Richard Guy of the University of Calgary . Prof. Marti n

Hellman of Stanford University . Dr. David Johnson of ATkT Bell Labo-

ratories . Prof. S . Lakshmivarahan of the University of Oklahoma, Dr . Ajie

Lenstra . of Bell Communication Research . Prof. Hendrik Lenstra Jr . of the

University of California at Berkeley . Prof. Roger Needham and Dr . Richar d

Pinch of the University of Cambridge . Dr . Peter Pleasants of the Univer-

sity of the South Pacific (Fiji), Prof . Carl Pomerance of the University o f

Georgia, Dr . Herman to Riede of the Centre for Mathematics and Compute r

Science (CWI), Amsterdam, and Prof . Hugh William of the University of

Manitoba . Finally . I would like to thank Mr . William Bloodworth (Dallas ,

Texas) . Dr . John Cosgrave (St . Patrick's College, Dublin) . Dr . Gavin Doherty

(Rutherford Appleton Laboratory, Oxfordshire) . Mr . Robert Pargeter (Tiver-

ton, Devon) . Mr . Alexandros Papanikolaou (Aston University, Birmingham) .

Yan S. Y. - Number Theory For Computing.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: