Algorithmic Number Theory
The goal of this class is to review three important questions in
algorithmic number theory: primality testing, the discrete logarithm
problem in GF(pn)*, and algorithms for lattices.
The first of these topics has come to a satisfactory solution in
theory and in practice, while on the contrary the last two have
developed at a fast pace over the last 5 years.
Outline of the class:
Prerequisites: Good knowledge of the rings Z/nZ. Though
the fist class will be devoted to this, a basic knowledge of computer
algebra (fast arithmetic, gcd computations) is preferable.
- Math/Computer algebra prerequisites: fast arithmetic, finite fields, ...
- Primality testing
Compositeness testing: Fermat, Dubois-Selfridge-Miller-Rabin
Group-based primality testing I: N-1, N+1. Application to Mersenne primes
Group-based primality testing II: Elliptic curves based primality testing: Goldwasser-Killian, ECPP.
Primes is in P: the AKS primality test.
- Discrete logarithms
Definition, applications in cryptology
Exponential-time methods: Pollard rho, baby step giant step
Interlude: sparse linear algebra
Subexponential (L(1/2)) methods for GF(q)*
Quasi-polynomial method for GF(pn)*, p small
- Algorithms for lattices
Definitions, basic algorithmic problems
The LLL lattice basis reduction algorithm
Babai algorithm, Kannan's embedding for CVP