Next:
Contents
Contents
Index
Elementary Number Theory,
A Computational Approach
William Stein
Date:
March 2007
To my wife Clarita Lefthand.
Contents
Preface
Prime Numbers
Prime Factorization
Primes
The Greatest Common Divisor
Numbers Factor as Products of Primes
The Fundamental Theorem of Arithmetic
The Sequence of Prime Numbers
There Are Infinitely Many Primes
Enumerating Primes
The Largest Known Prime
Primes of the Form
How Many Primes are There?
Exercises
The Ring of Integers Modulo
Congruences Modulo
Linear Equations Modulo
Fermat's Little Theorem
Wilson's Theorem
The Chinese Remainder Theorem
Multiplicative Functions
Quickly Computing Inverses and Huge Powers
How to Solve
How to Compute
Primality Testing
The Structure of
Polynomials over
Existence of Primitive Roots
Artin's Conjecture
Computing Primitive Roots
Exercises
Public-Key Cryptography
The Diffie-Hellman Key Exchange
The Discrete Log Problem
Realistic Diffie-Hellman Example
The Man in the Middle Attack
The RSA Cryptosystem
How RSA works
Encoding a Phrase in a Number
Some Complete Examples
Attacking RSA
Factoring
Given
When
and
are Close
Factoring
Given
Further Remarks
Exercises
Quadratic Reciprocity
Statement of the Quadratic Reciprocity Law
Euler's Criterion
First Proof of Quadratic Reciprocity
Euler's Proposition
Proof of Quadratic Reciprocity
A Proof of Quadratic Reciprocity Using Gauss Sums
Proof of Quadratic Reciprocity
Finding Square Roots
Exercises
Continued Fractions
Finite Continued Fractions
Partial Convergents
The Sequence of Partial Convergents
Every Rational Number is Represented
Infinite Continued Fractions
The Continued Fraction Procedure
Convergence of Infinite Continued Fractions
The Continued Fraction of
Preliminaries
Two Integral Sequences
A Related Sequence of Integrals
Extensions of the Argument
Quadratic Irrationals
Periodic Continued Fractions
Continued Fractions of Algebraic Numbers of Higher Degree
Recognizing Rational Numbers From Their Decimal Expansion
Sums of Two Squares
Exercises
Elliptic Curves
The Definition
The Group Structure on an Elliptic Curve
Integer Factorization Using Elliptic Curves
Pollard's
-Method
Motivation for the Elliptic Curve Method
Lenstra's Elliptic Curve Factorization Method
Examples
A Heuristic Explanation
Elliptic Curve Cryptography
Elliptic Curve Analogues of Diffie-Hellman
The ElGamal Cryptosystem and Digital Rights Management
The Elliptic Curve Discrete Logarithm Problem
Elliptic Curves Over the Rational Numbers
The Torsion Subgroup of
and the Rank
The Congruent Number Problem
Exercises
Answers and Hints
Bibliography
Index
About this document ...
William 2007-06-01
