Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 31

The author discuss about number-theoretic algorithms in this chapter. The author defines the concept of divisibility and divisors. The author also defines the concept of prime and composite numbers. The author provides division theorem, then proves it. The author defines remainders, common divisors and greatest common divisors, relatively prime integers and unique factorization.

The author then provides Euclid's algorithm to find greatest common divisor and state and prove its running time.

The author defines finite groups and subgroup and proves some theorems on it.

The author then discusses how to solve modular linear equations. The author proves some theorems and corollaries.

The author then describes the Chinese Remainder Theorem and prove it along with some corollaries.

The authors then discuss modular arithmetic with powers of an element instead of multiplication. The author states Euler's, Fermat's and Discrete logarithm theorem.

The authors then define RSA public-key cryptosystem and proves its correctness.

The authors then discuss primality testing and provides prime number theorem which provides details of density of prime numbers. The author provides pseudo-primality test and miller-rabin randomized primality test.

The author discusses the problem of integer factorization and provides Pollard's rho heuristic.