A Course in Computational Number Theory

A Course in Computational Number Theory uses the computer as a tool for motivation and explanation. The book is designed for the reader to quickly access a computer and begin doing personal experiments with the patterns of the integers. It presents and explains many of the fastest algorithms for working with integers. Traditional topics are covered, but the text also explores factoring algorithms, primality testing, the RSA public–key cryptosystem, and unusual applications such as check digit schemes and a computation of the energy that holds a salt crystal together. Advanced topics include continued fractions, Pell′s equation, and the Gaussian primes.
The CD–ROM contains a Mathematica? package that has hundreds of functions that show step–by–step operation of famous algorithms. (The user must have Mathematica in order to use this package.) Also included is an auxiliary package that contains a database of all 53,000 integers below 10^16 that are 2– and 3–strong pseudoprimes. Users will also have access to an online guide that gives illustrative examples of each function.

Spis treści:
Preface  v
Notation  xi
Chapter 1 Fundamentals  1
1.0  Introduction  1
1.1  A Famous Sequence of Numbers  2
1.2  The Euclidean ALgorithm  6
The Oldest Algorithm
Reversing the Euclidean Algorithm
The Extended GCD Algorithm
The Fundamental Theorem of Arithmetic
Two Applications
1.3  Modular Arithmetic  25
1.4  Fast Powers  30
A Fast Alforithm for ExponentiationPowers of Matrices, Big–O Notation
Chapter 2  Congruences, Equations, and Powers  41
2.0  Introduction  41
2.1  Solving Linear Congruences  41
Linear Diophantine Equations in Two Variables
The Conductor
An Importatnt Quadratic Congruence
2.2  The Chinese Remainder Theorem  49
2.3  PowerMod Patterns  55
Fermat′s Little Theorem
More Patterns in Powers
2.4  Pseudoprimes  59
Using the Pseudoprime Test
Chapter 3  Euler′s Function
3.0 Introduction  65
3.1  Euler′s Function  65
3.2  Perfect Numbers and Their Relatives  72
The Sum of Divisors Function
Perfect Numbers
Amicalbe, Abundant, and Deficient Numbers
3.3 Euler′s Theorem  81
3.4 Primitive Roots for Primes  84
The order of an Integer
Primes Have PRimitive roots
Repeating Decimals
3.5  Primitive Roots for COmposites  90
3.6  The Universal Exponent  93
Universal Exponents
Power Towers
The Form of Carmichael Numbers
Chapter 4  Prime Numbers  99
4.0  Introduction  99
4.1  The Number of Primes  100
We′ll Never Run Out of Primes
The Sieve of Eratosthenes
Chebyshev′s Theorem and Bertrand′s Postulate
4.2  Prime Testing and Certification  114
Strong Pseudoprimes
Industrial–Grade Primes
Prime Certification Via Primitive Roots
An Improvement
Pratt Certificates
4.3  Refinements and Other Directions  131
Other PRimality Tests
Strong Liars are Scarce
Finding the nth Prime
4.4  A Doszen Prime Mysteries  141
Chapter 5  Some Applications  145
5.0  Introduction  145
5.1  Coding Secrets  145
Tossing a Coin into a Well
The RSA Cryptosystem
Digital Signatures
5.2  The Yao Millionaire Problem  155
5.3  Check Digits  158
Basic Check Digit Schemes
A Perfect Check Digit Method
Beyond Perfection: Correcting Errors
5.4  Factoring Algorithms  167
Trial Division
Fermat′s Algorithm
Pollard Rho
Pollard p–1
The Current Scene
Chapter 6  Quadratic Residues  179
6.0  Introduction  179
6.1  P epin′s Test  179
Quadratic Residues
Pepin′s Test
Primes Congruent to 1 (Mod 40
6.2  Proof of Quadratic Reciprocity  185
Gauss′s Lemma
Proof of Quadratic Recipocity
Jacobi′s Extension
An Application to Factoring
6.3  Quadratic Equations  195
Chapter 7 Continuec Faction  201
7.0  Introduction  201
7.1  FInite COntinued Fractions  202
7.2  Infinite Continued Fractions  207
7.3  Periodic Continued Fractions  213
7.4  Pell′s Equation  227
7.5  Archimedes and the Sun God′s Cattle  232
Wurm′s Version: Using Rectangular Bulls
The Real Cattle Problem
7.6  Factoring via Continued Fractions  238
Chapter 8  Prime Testing with Lucas Sequences 247
8.0  Introduction  247
8.1  Divisibility Properties of Lucas Sequencese  248
8.2  Prime Tests Using Lucas Sequencesse  259
Lucas Certification
The Lucas–Lehmer Algorithm Explained
Luca Pseudoprimes
Strong Quadratic Pseudoprimes
Primality Testing′s Holy Grail
Chapter 9  Prime Imaginaries and Imaginary Primes  279
9.0  Introduction  279
9.1  Sums of Two Squares  279
9.2  The Gaussian Intergers  302
Complex Number Theory
Gaussian Primes
The Moat Problem
The Gaussian Zoo
9.3  Higher Reciprocity  325
Appendix A. Maathematica Basics  333
1.0  Introduction  333
A.1  Plotting  335
A.2  Typesetting  338
Sending Files By E–Mail
A.3  Types of Functions  341
A.4  Lists  343
A.5 Programs  345
A.6 Solving Equations  347
A.7  Symbolic Algebra  349
Appendix B  Lucas Certificates Exist  351
References  355
Index of Mathematica Objects  359
Subject Index  363
&# 160;