Elementary Number Theory: Primes, Congruences, and Secrets: A Computational Approach (Undergraduate Texts in Mathematics)

✍ Scribed by William Stein

• Publisher: Springer
• Year: 2008
• Tongue: English
• Leaves: 177
• Edition: 2009
• Category: Library

✦ Synopsis

This is a book about prime numbers, congruences, secret messages, and elliptic curves that you can read cover to cover. It grew out of undergr- uate courses that the author taught at Harvard, UC San Diego, and the University of Washington. The systematic study of number theory was initiated around 300B. C. when Euclid proved that there are in?nitely many prime numbers, and also cleverly deduced the fundamental theorem of arithmetic, which asserts that every positive integer factors uniquely as a product of primes. Over a thousand years later (around 972A. D. ) Arab mathematicians formulated the congruent number problem that asks for a way to decide whether or not a given positive integer n is the area of a right triangle, all three of whose sides are rational numbers. Then another thousand years later (in 1976), Di?e and Hellman introduced the ?rst ever public-key cryptosystem, which enabled two people to communicate secretely over a public communications channel with no predeterminedsecret; this invention and the ones that followed it revolutionized the world of digital communication. In the 1980s and 1990s, elliptic curves revolutionized number theory, providing striking new insights into the congruent number problem, primality testing, publ- key cryptography, attacks on public-key systems, and playing a central role in Andrew Wiles’ resolution of Fermat’s Last Theorem.

✦ Table of Contents

Cover
Undergraduate Texts in Mathematics (series)
Elementary Number Theory: Primes, Congruences, and Secrets: A Computational Approach
Copyright
Dedication
Contents
Preface
Prime Numbers
Prime Factorization
The Sequence of Prime Numbers
Exercises
The Ring of Integers Modulo n
Congruences Modulo n
The Chinese Remainder Theorem
Quickly Computing Inverses and Huge Powers
Primality Testing
The Structure of (Z/pZ)*
Exercises
Public-key Cryptography
Playing with Fire
The Diffie-Hellman Key Exchange
The RSA Cryptosystem
Attacking RSA
Exercises
Quadratic Reciprocity
Statement of the Quadratic Reciprocity Law
Euler's Criterion
First Proof of Quadratic Reciprocity
A Proof of Quadratic Reciprocity Using Gauss Sums
Finding Square Roots
Exercises
Continued Fractions
The Definition
Finite Continued Fractions
Infinite Continued Fractions
The Continued Fraction of e
Quadratic Irrationals
Recognizing Rational Numbers
Sums of Two Squares
Exercises
Elliptic Curves
The Definition
The Group Structure on an Elliptic Curve
Integer Factorization Using Elliptic Curves
Elliptic Curve Cryptography
Elliptic Curves Over the Rational Numbers
Exercises
Answers and Hints
References
Index
Undergraduate Texts in Mathematics (continued)