SymbolicComputing

Integer Arithmetic

• Karatsuba's multiplication algorithm
• Extended Euclidean algoritm

Integer Factorization

• Wheel factorization

Modular Arithmetic

• Find multiplicative inverse with Extended Euclidean algorithm

Prime Numbers

• Sieve of Eratosthenes
• Bengalloun's incremental sieve
• Pritchard's Wheel Sieve
• Rabin-Miller Test
• Lucas primality test

Polynomial Arithmetic

• Kronecker's method to factor a polynomial $a(x) \in \mathbb{Z}[x]$ such that $a(0) \neq 0$
• Lensta-Lenstra-Lovász lattice basis reduction algorithm