Algorithmic Number Theory

Contents

Chap. 1: The Fibonacci Numbers

(Cf. [3], Chap. 3)
Fast exponentiation algorithm,
fast algorithm for the calculation of the Fibonacci numbers,
growth of Fibonacci numbers.

Example code: fibo.ari
 

Chap. 2: The Euclidean Algorithm

(Cf. [3], Chaps 4,5)
Classical Euclidean algorithm, extended Euclidean algorithm
Complexity of the algorithm (proof uses Fibonacci numbers)
Euclidean rings, examples: Z, Gaussian integers Z[i], polynomial ring K[X]
Irreducible elements, prime elements, prime factorization

Example code: gcd.ari
 

Chap. 3: The Rings Z/m

(Cf. [3], Chap 6)
Congruence modulo m
Invertible elements of Z/m, calculation by extended Euclidean algorithm
Isomorphism Z/m --> Z/m₁ x ... x Z/m_r if m = m₁...m_r with pairwise coprime m_i
Construction of the inverse of this isomorphism
Cyclic groups

Example code: chin.ari
 

Chap. 4: Structure of (Z/m)*, Primitive Roots

(Cf. [3], Chap 7)
For every prime p, the multipicative group (Z/p)* is cyclic.
A generator of this group is called a primitive root modulo p.
More generally, every finite subgroup of the multiplicative group of a field is cyclic.
For odd primes p, the groups (Z/p^k)* are cyclic for all k >= 1.
The groups (Z/2^k)* are not cyclic for k >= 3, but isomorphic to a product of a cyclic group of order 2^k-2 and a cyclic group of order 2.

Example code: primroot.ari
 

Chap 5: The Discrete Logarithm

Notes (dvi) (ps)
 

Chap 6: Little Fermat and Deterministic Primality Tests

(Cf. [3], Chap. 10)
Little theorem of Fermat,
Definition and characterization of Carmichael numbers.
Theorem: An integer N > 2 is prime iff there exists an integer a such that
i)   a^N-1 = 1 mod N,
ii)  a^(N-1)/q /= 1 mod N for all prime divisors q | N-1.
Generalization of this theorem, if only part of the prime factorization of N-1 is known.
 

Chap 7: Pollard's (p-1)-Factorization Algorithm

(Cf. [3], Chap. 14)
This algorithm usually finds a factor of a composite number N if there is a prime factor p | N such that the prime decomposition of p-1 contains only prime powers q^k <= B, where B is a (relatively) small constant. Then, if Q is the product of all prime powers <= B, one has x^Q = 1 mod p for all x coprime to p. Therefore, if x^Q /= 1 mod N, then d := gcd(x^Q - 1, N) is a non-trivial factor of N.
'Big prime variation' of this algorithm.

Example code: p1factor.ari
 

Chap 8: Quadratic Residues, Quadratic Reciprocity Law

Notes (dvi) (ps)
(Cf. [3], Chap. 11)

Example code: jacobi.ari
 

Chap 9: Probabilistic Primality Tests

(Cf. [3], Chap. 12)
Solovay-Strassen test
Miller-Rabin test

Example code: probtest.ari
 

Chap 10: Quadratic Extensions, (p+1)-Primality Test

(Cf. [3], Chaps. 16, 17)

 

Chap 11: The Quadratic Sieve Factorization Algorithm

(Cf. [2], Chap. 10.4)

 

Chap 12: More Algorithms for the Discrete Logarithm

Pollard's lambda method
Index calculus
 

Chap 13: Elliptic Curves

(Cf. [3], Chap. 19)

Example code: ellfact.ari
 

Chap 14: Polynomials over Finite Fields

 

Chap 15: Factorization of Polynomials over Finite Fields

 

Chap 16: Finite Fields of Characteristic 2

 

Literature

1. E. Bach and J. Shallit: Algorithmic Number Theory, Vol. I. MIT Press
2. H. Cohen: A Course in Computational Algebraic Number Theory. Springer-Verlag
3. O. Forster: Algorithmische Zahlentheorie, Vieweg-Verlag
4. P. Giblin: Primes and Programming. An Introduction to Number Theory with Computing. Cambridge UP
5. D. Knuth: The Art of Computer Programming, Vol 2. Seminumerical algorithms. Addison-Wiley
6. H. Riesel: Prime Numbers and Computer Methods for Factorization. Birkhäuser