| 1. | Euclidean Algorithm | Used to compute the greatest common divisor (GCD) of two integers. |
| 2. | Extended Euclidean Algorithm | Extends the Euclidean algorithm to compute the integer coefficients of Bézout’s identity. |
| 3. | Sieve of Eratosthenes | A simple, ancient algorithm for finding all prime numbers up to a specified integer. |
| 4. | Chinese Remainder Theorem | Breaks down larger problems into smaller ones to calculate remainders of separate moduli. |
| 5. | Fermat’s Factorization Method | Factorizes an odd integer as the difference of two squares. |
| 6. | Pollard’s rho algorithm | An algorithm that outputs the prime factors of a composite number. |
| 7. | Binary Exponentiation | Square and multiply method to calculate powers of a number in logarithmic time. |
| 8. | Miller–Rabin primality test | Checks if a given number is a prime, with a probability of error. |
| 9. | Euler’s Totient function | Calculates the count of numbers less than ‘n’ that are relatively prime to ‘n’. |
| 10. | Fast Fourier Transform (FFT) | Efficiently solve problems related to polynomial multiplications. |
| 11. | Fermat’s Little Theorem | Used to check the primality of a number. |
| 12. | Wilson’s Theorem | Used to check the primality of a number. |
| 13. | Newton–Raphson method | Method for finding successively better approximations to the roots of a real-valued function. |
| 14. | Lucas–Lehmer primality test | Primality test for Mersenne numbers. |
| 15. | Lenstra elliptic-curve factorization | An algorithm for factorizing integers using elliptic curves. |
| 16. | Goldwasser–Micali algorithm | An algorithm for the encryption of single bits. |
| 17. | Sieve of Sundaram | An algorithm to eliminate certain integers of the form i + j + 2ij where i,j ∈ N. |
| 18. | Quadratic Sieve | Fast, general purpose factoring algorithm; considered one of the most efficient for extracting small to medium size primes. |
| 19. | AKS primality test | Deterministically checks if a number is prime in polynomial time. |
| 20. | Shanks’ square forms factorization (SQUFOF) | Algorithm for integer factorization, based on the observation that square roots of square numbers are integral. |
