ABSTRACT

This book is an introduction to the algorithmic aspects of number theory and its applications to cryptography, with special emphasis on the RSA cryptosys-tem. It covers many of the familiar topics of elementary number theory, all with an algorithmic twist. The text also includes many interesting historical notes.

chapter 1|2 pages

Cryptography

chapter 2|2 pages

The RSA cryptosystem

chapter 3|2 pages

Computer algebra

chapter 4|1 pages

The Greeks and the integers

chapter 5|3 pages

Fermat, Euler, and Gauss

chapter 6|1 pages

The problems of number theory

chapter 7|5 pages

Theorems and proofs

chapter 1|16 pages

Fundamental algorithms

chapter 2|16 pages

Unique factorization

chapter 3|14 pages

Prime numbers

chapter 4|16 pages

Modular arithmetic

chapter 5|16 pages

Induction and Fermat

chapter 6|12 pages

Pseudoprimes

chapter 7|14 pages

Systems of Congruences

chapter 8|20 pages

Groups

chapter 9|10 pages

Mersenne and Fermat

chapter 10|12 pages

Primality tests and primitive roots

chapter 11|12 pages

The RSA cryptosystem

chapter |4 pages

Coda

chapter 1|1 pages

Square roots

chapter 2|3 pages

Power algorithm