Cryptography is a key technology in electronic security systems. Modern cryptograpic techniques have many uses, such as to digitally sign documents, for access control, to implement electronic money, and for copyright protection. Because of these important uses it is necessary that users be able to estimate the efficiency and security of cryptographic techniques. It is not sufficient for them to know only how the techniques work. This book is written for readers who want to learn about mod- ern cryptographic algorithms and their mathematical foundation but who do not have the necessary mathematical background. It is my goal to explain the basic techniques of modern cryptography, including the necessary mathematical results from linear algebra, algebra, number theory, and probability theory. I assume only basic mathematical knowledge. The book is based on courses in cryptography that I have been teaching at the Technical University, Darmstadt, since 1996. I thank all students who attended the courses and who read the manuscript carefully for their interest and support. In particular, I would like to thank Harald Baier, Gabi Barking, Manuel Breuning, Sa- fuat Hamdy, Birgit Henhapl, Michael Jacobson (who also corrected my English), Andreas Kottig, Markus Maurer, Andreas Meyer, Stefan v vi Preface Neis, Sachar Paulus, Thomas Pfahler, Marita Skrobic, Edlyn Thske, Patrick Theobald, and Ralf-Philipp Weinmann. I also thank the staff at Springer-Verlag, in particular Martin Peters, Agnes Herrmann, Claudia Kehl, Ina Lindemann, and Thrry Kornak, for their support in the preparation of this book.

This book reproduces, with minor changes, the notes prepared for a course given at Brigham Young University during the academic year 1984-1985. It is intended to be an introduction to the theory of numbers. The audience consisted largely of undergraduate students with no more background than high school mathematics. The presentation was thus kept as elementary and self-contained as possible. However, because the discussion was, generally, carried far enough to introduce the audience to some areas of current research, the book should also be useful to graduate students. The only prerequisite to reading the book is an interest in and aptitude for mathe matics. Though the topics may seem unrelated, the study of diophantine equations has been our main goal. I am indebted to several mathematicians whose published as well as unpublished work has been freely used throughout this book. In particular, the Phillips Lectures at Haverford College given by Professor John T. Tate have been an important source of material for the book. Some parts of Chapter 5 on algebraic curves are, for example, based on these lectures."

From its birth (in Babylon?) till 1936 the theory of quadratic forms dealt almost exclusively with forms over the real field, the complex field or the ring of integers. Only as late as 1937 were the foundations of a theory over an arbitrary field laid. This was in a famous paper by Ernst Witt. Still too early, apparently, because it took another 25 years for the ideas of Witt to be pursued, notably by Albrecht Pfister, and expanded into a full branch of algebra. Around 1960 the development of algebraic topology and algebraic K-theory led to the study of quadratic forms over commutative rings and hermitian forms over rings with involutions. Not surprisingly, in this more general setting, algebraic K-theory plays the role that linear algebra plays in the case of fields. This book exposes the theory of quadratic and hermitian forms over rings in a very general setting. It avoids, as far as possible, any restriction on the characteristic and takes full advantage of the functorial aspects of the theory. The advantage of doing so is not only aesthetical: on the one hand, some classical proofs gain in simplicity and transparency, the most notable examples being the results on low-dimensional spinor groups; on the other hand new results are obtained, which went unnoticed even for fields, as in the case of involutions on 16-dimensional central simple algebras. The first chapter gives an introduction to the basic definitions and properties of hermitian forms which are used throughout the book.

This volume contains the refereed proceedings of the Workshop on Cryptography and Computational Number Theory, CCNT'99, which has been held in Singapore during the week of November 22-26, 1999. The workshop was organized by the Centre for Systems Security of the Na tional University of Singapore. We gratefully acknowledge the financial support from the Singapore National Science and Technology Board under the grant num ber RP960668/M. The idea for this workshop grew out of the recognition of the recent, rapid development in various areas of cryptography and computational number the ory. The event followed the concept of the research programs at such well-known research institutions as the Newton Institute (UK), Oberwolfach and Dagstuhl (Germany), and Luminy (France). Accordingly, there were only invited lectures at the workshop with plenty of time for informal discussions. It was hoped and successfully achieved that the meeting would encourage and stimulate further research in information and computer security as well as in the design and implementation of number theoretic cryptosystems and other related areas. Another goal of the meeting was to stimulate collaboration and more active interaction between mathematicians, computer scientists, practical cryptographers and engineers in academia, industry and government."

This book is an outgrowth of the Workshop on "Regulators in Analysis, Geom etry and Number Theory" held at the Edmund Landau Center for Research in Mathematical Analysis of The Hebrew University of Jerusalem in 1996. During the preparation and the holding of the workshop we were greatly helped by the director of the Landau Center: Lior Tsafriri during the time of the planning of the conference, and Hershel Farkas during the meeting itself. Organizing and running this workshop was a true pleasure, thanks to the expert technical help provided by the Landau Center in general, and by its secretary Simcha Kojman in particular. We would like to express our hearty thanks to all of them. However, the articles assembled in the present volume do not represent the proceedings of this workshop; neither could all contributors to the book make it to the meeting, nor do the contributions herein necessarily reflect talks given in Jerusalem. In the introduction, we outline our view of the theory to which this volume intends to contribute. The crucial objective of the present volume is to bring together concepts, methods, and results from analysis, differential as well as algebraic geometry, and number theory in order to work towards a deeper and more comprehensive understanding of regulators and secondary invariants. Our thanks go to all the participants of the workshop and authors of this volume. May the readers of this book enjoy and profit from the combination of mathematical ideas here documented."

Rigid (analytic) spaces were invented to describe degenerations, reductions, and moduli of algebraic curves and abelian varieties. This work, a revised and greatly expanded new English edition of an earlier French text by the same authors, presents important new developments and applications of the theory of rigid analytic spaces to abelian varieties, "points of rigid spaces," etale cohomology, Drinfeld modular curves, and Monsky-Washnitzer cohomology. The exposition is concise, self-contained, rich in examples and exercises, and will serve as an excellent graduate-level text for the classroom or for self-study."

February 14, 1968 marked the thirtieth year since the death of Edmund Landau. The papers of this volume are dedicated by friends, students, and admirers to the memory of this outstanding scholar and teacher. To mention but one side of his original and varied scientific work, the results and effects of which cannot be dis cussed here, Edmund Landau performed one of his greatest services in developing the analytic theory of prime numbers from a subject accessible only with great difficulty even to the initiated few to the general estate of mathematicians. With the exception of the work of Chebyshev, Riemann, and Mertens, before Landau the problems of this theory were attempted only in a number of papers which were filled with gaps and errors. These problems were such that even Gauss abandoned them after several attempts in his youth, and they were described by N. H. Abel in a letter of 1823 and by O. Toeplitz in a lecture in 1930 as the deepest part of mathe matics. Clarification first began with the papers of Hadamard, de la Vallee Poussin, and von Mangoldt. At the end ofthe foreword to his work" Handbuch der Lehre von der Verteilung der Primzahlen" which appeared in 1909, Landau could thus remark with complete justification: " . . . The difficulty of the previously unsolved problems has frightened nearly everyone away from the theory of prime numbers.

Like other introductions to number theory, this one includes the usual curtsy to divisibility theory, the bow to congruence, and the little chat with quadratic reciprocity. It also includes proofs of results such as Lagrange's Four Square Theorem, the theorem behind Lucas's test for perfect numbers, the theorem that a regular n-gon is constructible just in case phi(n) is a power of 2, the fact that the circle cannot be squared, Dirichlet's theorem on primes in arithmetic progressions, the Prime Number Theorem, and Rademacher's partition theorem. We have made the proofs of these theorems as elementary as possible. Unique to The Queen of Mathematics are its presentations of the topic of palindromic simple continued fractions, an elementary solution of Lucas's square pyramid problem, Baker's solution for simultaneous Fermat equations, an elementary proof of Fermat's polygonal number conjecture, and the Lambek-Moser-Wild theorem.

A gentle introduction to the highly sophisticated world of discrete mathematics, Mathematical Problems and Proofs presents topics ranging from elementary definitions and theorems to advanced topics -- such as cardinal numbers, generating functions, properties of Fibonacci numbers, and Euclidean algorithm. This excellent primer illustrates more than 150 solutions and proofs, thoroughly explained in clear language. The generous historical references and anecdotes interspersed throughout the text create interesting intermissions that will fuel readers' eagerness to inquire further about the topics and some of our greatest mathematicians. The author guides readers through the process of solving enigmatic proofs and problems, and assists them in making the transition from problem solving to theorem proving. At once a requisite text and an enjoyable read, Mathematical Problems and Proofs is an excellent entree to discrete mathematics for advanced students interested in mathematics, engineering, and science.

"Et moi, ..., si j'avait su comment en revenir, je One service mathematics bas rendered the human race. It bas put common sense back n'y serais point all~.' where it belongs, on the topmost shelf next to lu1esVeme the dusty canister labelled 'discarded nonsense'~ Eric T. Bell 1be series is divergent; therefore we may be able to do something with it O. Heaviside Mathematics is a tool for thought. A highly necessary tool in a world where both feedback and nonlineari- ties abound. Similarly, all kinds of parts of mathematics serve as tools for other parts and for other sci- ences. Applying a simple rewriting rule to the quote on the right above one finds such statements as: 'One ser- vice topology has rendered mathematical physics ...'; 'One service logic has rendered computer science ...'; 'One service category theory has rendered mathematics ...'. All arguably true. And all statements obtainable this way form part of the raison d 'etre of this series.

Recent Developments in Infinite-Dimensional Analysis and Quantum Probability is dedicated to Professor Takeyuki Hida on the occasion of his 70th birthday. The book is more than a collection of articles. In fact, in it the reader will find a consistent editorial work, devoted to attempting to obtain a unitary picture from the different contributions and to give a comprehensive account of important recent developments in contemporary white noise analysis and some of its applications. For this reason, not only the latest results, but also motivations, explanations and connections with previous work have been included. The wealth of applications, from number theory to signal processing, from optimal filtering to information theory, from the statistics of stationary flows to quantum cable equations, show the power of white noise analysis as a tool. Beyond these, the authors emphasize its connections with practically all branches of contemporary probability, including stochastic geometry, the structure theory of stationary Gaussian processes, Neumann boundary value problems, and large deviations.

viii 2. As a natural continuation of the section on the Platonic solids, a detailed and complete classi?cation of ?nite Mobius ] groupsal a Klein has been given with the necessary background material, such as Cayley s theorem and the Riemann Hurwitz relation. 3. Oneofthemostspectaculardevelopmentsinalgebraandge- etry during the late nineteenth century was Felix Klein s theory of the icosahedron and his solution of the irreducible quintic in termsofhypergeometricfunctions.Aquick, direct, andmodern approach of Klein s main result, the so-called Normalformsatz, has been given in a single large section. This treatment is in- pendent of the material in the rest of the book, and is suitable for enrichment and undergraduate/graduate research projects. All known approaches to the solution of the irreducible qu- tic are technical; I have chosen a geometric approach based on the construction of canonical quintic resolvents of the equation of the icosahedron, since it meshes well with the treatment of the Platonic solids given in the earlier part of the text. An - gebraic approach based on the reduction of the equation of the icosahedron to the Brioschi quintic by Tschirnhaus transfor- tions is well documented in other textbooks. Another section on polynomial invariants of ?nite Mobius ] groups, and two new appendices, containing preparatory material on the hyper- ometric differential equation and Galois theory, facilitate the understanding of this advanced material."

Computations with Markov Chains presents the edited and reviewed proceedings of the Second International Workshop on the Numerical Solution of Markov Chains, held January 16--18, 1995, in Raleigh, North Carolina. New developments of particular interest include recent work on stability and conditioning, Krylov subspace-based methods for transient solutions, quadratic convergent procedures for matrix geometric problems, further analysis of the GTH algorithm, the arrival of stochastic automata networks at the forefront of modelling stratagems, and more. An authoritative overview of the field for applied probabilists, numerical analysts and systems modelers, including computer scientists and engineers.

Srinivasa Ramanujan is, arguably, the greatest mathematician that India has produced. His story is quite unusual: although he had no formal education inmathematics, he taught himself, and managed to produce many important new results. With the support of the English number theorist G. H. Hardy, Ramanujan received a scholarship to go to England and study mathematics. He died very young, at the age of 32, leaving behind three notebooks containing almost 3000 theorems, virtually all without proof. G. H. Hardy and others strongly urged that notebooks be edited and published, and the result is this series of books. This volume dealswith Chapters 1-9 of Book II; each theorem is either proved, or a reference to a proof is given.

In the modern age of almost universal computer usage, practically every individual in a technologically developed society has routine access to the most up-to-date cryptographic technology that exists, the so-called RSA public-key cryptosystem. A major component of this system is the factorization of large numbers into their primes. Thus an ancient number-theory concept now plays a crucial role in communication among millions of people who may have little or no knowledge of even elementary mathematics. The independent structure of each chapter of the book makes it highly readable for a wide variety of mathematicians, students of applied number theory, and others interested in both study and research in number theory and cryptography.

Over the last decade, the role of computational simulations in all aspects of aerospace design has steadily increased. However, despite the many advances, the time required for computations is far too long. This book examines new ideas and methodologies that may, in the next twenty years, revolutionize scientific computing. The book specifically looks at trends in algorithm research, human computer interface, network-based computing, surface modeling and grid generation and computer hardware and architecture. The book provides a good overview of the current state-of-the-art and provides guidelines for future research directions. The book is intended for computational scientists active in the field and program managers making strategic research decisions.

The numerous explicit formulae of the classical theory of quadratic forms revealed remarkable multiplicative properties of the numbers of integral representations of integers by positive definite integral quadratic forms. These properties were explained by the original theory of Hecke operators. As regards the integral representations of quadratic forms in more than one variable by quadratic forms, no multiplicative properties were known at that time, and so there was nothing to explain. However, the idea of Hecke operators was so natural and attractive that soon attempts were made to cultivate it in the neighbouring field of modular forms of several variables. The approach has proved to be fruitful; in particular, a number of multiplicative properties of integral representations of quadratic forms by quadratic forms were eventually discovered. By now the theory has reached a certain maturity, and the time has come to give an up-to-date report in a concise form, in order to provide a solid ground for further development. The purpose of this book is to present in the form of a self-contained text-book the contemporary state of the theory of Hecke operators on the spaces of hoi om orphic modular forms of integral weight (the Siegel modular forms) for congruence subgroups of integral symplectic groups. The book can also be used for an initial study of modular forms of one or several variables and theta-series of positive definite integral quadratic forms.

This is a second edition of Lang's well-known textbook. It covers all of the basic material of classical algebraic number theory, giving the student the background necessary for the study of further topics in algebraic number theory, such as cyclotomic fields, or modular forms.

"Lang's books are always of great value for the graduate student and the research mathematician. This updated edition of Algebraic number theory is no exception."--MATHEMATICAL REVIEWS

This volume is the offspring of a week-long workshop on "Galois groups over Q and related topics," which was held at the Mathematical Sciences Research Institute during the week March 23-27, 1987. The organizing committee consisted of Kenneth Ribet (chairman), Yasutaka Ihara, and Jean-Pierre Serre. The conference focused on three principal themes: 1. Extensions of Q with finite simple Galois groups. 2. Galois actions on fundamental groups, nilpotent extensions of Q arising from Fermat curves, and the interplay between Gauss sums and cyclotomic units. 3. Representations of Gal(Q/Q) with values in GL(2)j deformations and connections with modular forms. Here is a summary of the conference program: * G. Anderson: "Gauss sums, circular units and the simplex" * G. Anderson and Y. Ihara: "Galois actions on 11"1 ( *** ) and higher circular units" * D. Blasius: "Maass forms and Galois representations" * P. Deligne: "Galois action on 1I"1(P-{0, 1, oo}) and Hodge analogue" * W. Feit: "Some Galois groups over number fields" * Y. Ihara: "Arithmetic aspect of Galois actions on 1I"1(P - {O, 1, oo})" - survey talk * U. Jannsen: "Galois cohomology of i-adic representations" * B. Matzat: - "Rationality criteria for Galois extensions" - "How to construct polynomials with Galois group Mll over Q" * B. Mazur: "Deforming GL(2) Galois representations" * K. Ribet: "Lowering the level of modular representations of Gal( Q/ Q)" * J-P. Serre: - Introductory Lecture - "Degree 2 modular representations of Gal(Q/Q)" * J.

A conference on Analytic Number Theory and Diophantine Problems was held from June 24 to July 3, 1984 at the Oklahoma State University in Stillwater. The conference was funded by the National Science Foundation, the College of Arts and Sciences and the Department of Mathematics at Oklahoma State University. The papers in this volume represent only a portion of the many talks given at the conference. The principal speakers were Professors E. Bombieri, P. X. Gallagher, D. Goldfeld, S. Graham, R. Greenberg, H. Halberstam, C. Hooley, H. Iwaniec, D. J. Lewis, D. W. Masser, H. L. Montgomery, A. Selberg, and R. C. Vaughan. Of these, Professors Bombieri, Goldfeld, Masser, and Vaughan gave three lectures each, while Professor Hooley gave two. Special sessions were also held and most participants gave talks of at least twenty minutes each. Prof. P. Sarnak was unable to attend but a paper based on his intended talk is included in this volume. We take this opportunity to thank all participants for their (enthusiastic) support for the conference. Judging from the response, it was deemed a success. As for this volume, I take responsibility for any typographical errors that may occur in the final print. I also apologize for the delay (which was due to the many problems incurred while retyping all the papers). A. special thanks to Dollee Walker for retyping the papers and to Prof. W. H. Jaco for his support, encouragement and hard work in bringing the idea of the conference to fruition.

In this volume we present a survey of the theory of Galois module structure for rings of algebraic integers. This theory has experienced a rapid growth in the last ten to twelve years, acquiring mathematical depth and significance and leading to new insights also in other branches of algebraic number theory. The decisive take-off point was the discovery of its connection with Artin L-functions. We shall concentrate on the topic which has been at the centre of this development, namely the global module structure for tame Galois extensions of numberfields -in other words of extensions with trivial local module structure. The basic problem can be stated in down to earth terms: the nature of the obstruction to the existence of a free basis over the integral group ring ("normal integral basis"). Here a definitive pattern of a theory has emerged, central problems have been solved, and a stage has clearly been reached when a systematic account has become both possible and desirable. Of course, the solution of one set of problems has led to new questions and it will be our aim also to discuss some of these. We hope to help the reader early on to an understanding of the basic structure of our theory and of its central theme, and to motivate at each successive stage the introduction of new concepts and new tools.

Automorphic forms are an important complex analytic tool in number theory and modern arithmetic geometry. They played for example a vital role in Andrew Wiles's proof of Fermat's Last Theorem. This text provides a concise introduction to the world of automorphic forms using two approaches: the classic elementary theory and the modern point of view of adeles and representation theory. The reader will learn the important aims and results of the theory by focussing on its essential aspects and restricting it to the 'base field' of rational numbers. Students interested for example in arithmetic geometry or number theory will find that this book provides an optimal and easily accessible introduction into this topic.

During the academic year 1980-1981 I was teaching at the Technion-the Israeli Institute of Technology-in Haifa. The audience was small, but con sisted of particularly gifted and eager listeners; unfortunately, their back ground varied widely. What could one offer such an audience, so as to do justice to all of them? I decided to discuss representations of natural integers as sums of squares, starting on the most elementary level, but with the inten tion of pushing ahead as far as possible in some of the different directions that offered themselves (quadratic forms, theory of genera, generalizations and modern developments, etc.), according to the interests of the audience. A few weeks after the start of the academic year I received a letter from Professor Gian-Carlo Rota, with the suggestion that I submit a manuscript for the Encyclopedia of Mathematical Sciences under his editorship. I answered that I did not have a ready manuscript to offer, but that I could use my notes on representations of integers by sums of squares as the basis for one. Indeed, about that time I had already started thinking about the possibility of such a book and had, in fact, quite precise ideas about the kind of book I wanted it to be."

In the early years of the 1980s, while I was visiting the Institute for Ad vanced Study (lAS) at Princeton as a postdoctoral member, I got a fascinating view, studying congruence modulo a prime among elliptic modular forms, that an automorphic L-function of a given algebraic group G should have a canon ical p-adic counterpart of several variables. I immediately decided to find out the reason behind this phenomenon and to develop the theory of ordinary p-adic automorphic forms, allocating 10 to 15 years from that point, putting off the intended arithmetic study of Shimura varieties via L-functions and Eisenstein series (for which I visited lAS). Although it took more than 15 years, we now know (at least conjecturally) the exact number of variables for a given G, and it has been shown that this is a universal phenomenon valid for holomorphic automorphic forms on Shimura varieties and also for more general (nonholomorphic) cohomological automorphic forms on automorphic manifolds (in a markedly different way). When I was asked to give a series of lectures in the Automorphic Semester in the year 2000 at the Emile Borel Center (Centre Emile Borel) at the Poincare Institute in Paris, I chose to give an exposition of the theory of p-adic (ordinary) families of such automorphic forms p-adic analytically de pending on their weights, and this book is the outgrowth of the lectures given there."

Owing to the developments and applications of computer science, ma thematicians began to take a serious interest in the applications of number theory to numerical analysis about twenty years ago. The progress achieved has been both important practically as well as satisfactory from the theoretical view point. It'or example, from the seventeenth century till now, a great deal of effort was made in developing methods for approximating single integrals and there were only a few works on multiple quadrature until the 1950's. But in the past twenty years, a number of new methods have been devised of which the number theoretic method is an effective one. The number theoretic method may be described as follows. We use num ber theory to construct a sequence of uniformly distributed sets in the s dimensional unit cube G , where s ~ 2. Then we use the sequence to s reduce a difficult analytic problem to an arithmetic problem which may be calculated by computer. For example, we may use the arithmetic mean of the values of integrand in a given uniformly distributed set of G to ap s proximate the definite integral over G such that the principal order of the s error term is shown to be of the best possible kind, if the integrand satis fies certain conditions.