Number Theory and Primality

This group gathers numerical algorithms rooted in number theory, including primality testing such as the Miller-Rabin and AKS tests, integer factorization methods such as Pollard rho, the quadratic sieve, the general number field sieve and Lenstra elliptic-curve factorization, the Euclidean and extended Euclidean algorithms for greatest common divisors, modular arithmetic algorithms such as modular exponentiation and Montgomery modular multiplication, discrete logarithm algorithms such as baby-step giant-step and Pohlig-Hellman, the Chinese remainder theorem, classical multiplication and long division, and historical arithmetic systems and techniques for computing by hand. Their shared work is a computation whose correctness rests on properties of integers and modular arithmetic, as distinct from a checksum computed for error detection, which belongs to Checksum and Error Detection.