Elementary Number Theory Algorithms

In this course we present some algorithms for primality testing, factoring integers and solving the discrete logarithm problem, based on elementary number theory.

• Complexity of an algorithm: polynomial, exponential and subexponential algorithms. Examples: the extended Euclid algorithm, the calculations of powers by successive squarings.


• Primality tests: Miller-Rabin test. Construction of large pseudoprimes.


• Factoring algorithms: trial division, Pollard p-1, Pollard ρ.


• Discrete logarithm problem: Pollard ρ, Baby Step Giant Step, Pohlig-Hellman method, index calculus (time permitting).

References:

• R. Crandall, C. Pomerance, Prime Numbers. A computational perspective, Springer-Verlag 2002.
  
• R. Schoof, Four primality testing algorithms, “Algorithmic number theory” MSRI Publications 44, Cambridge University Press 2008, 101–126. pdf ( Miller-Rabin test is on pp. 2–4).
• Wikipedia: Miller-Rabin test link.
• Wikipedia: Pollard p-1 algorithm link.
• Wikipedia: Pollard ρ algorithm link.
• Wikipedia: Baby Step Giant Step link
• Wikipedia: Pohlig-Hellman algorithm link
• Wikipedia: Index calculus link

Prerequisites: An introductory course in algebra: basic properties of finite abelian groups, calculus modulo n.