Elementary Algorithmic Number Theory

References:

• Pari/GP (download) link
• 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.

Notes pdf

Exercises

• Exercises 1 (group theory) pdf    Solutions pdf
• Exercises 2 (group theory) pdf
• Exercises 3 (naif algorithm & Pollard ρ) pdf

Programs for the exercises

• Pari/GP (download) link
• naif link
• pollard rho link
• pollard rho showing iterates mod the smallest factor link
• comparison of Pollard rho and trial division link
• pminus link
• mrtest link