• Home
    Tables – Mathematics – Number Theoretic Algorithms

    No.####Algorithm Name########Description####
    1.Euclidean AlgorithmUsed to compute the greatest common divisor (GCD) of two integers.
    2.Extended Euclidean AlgorithmExtends the Euclidean algorithm to compute the integer coefficients of Bézout’s identity.
    3.Sieve of EratosthenesA simple, ancient algorithm for finding all prime numbers up to a specified integer.
    4.Chinese Remainder TheoremBreaks down larger problems into smaller ones to calculate remainders of separate moduli.
    5.Fermat’s Factorization MethodFactorizes an odd integer as the difference of two squares.
    6.Pollard’s rho algorithmAn algorithm that outputs the prime factors of a composite number.
    7.Binary ExponentiationSquare and multiply method to calculate powers of a number in logarithmic time.
    8.Miller–Rabin primality testChecks if a given number is a prime, with a probability of error.
    9.Euler’s Totient functionCalculates 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 TheoremUsed to check the primality of a number.
    12.Wilson’s TheoremUsed to check the primality of a number.
    13.Newton–Raphson methodMethod for finding successively better approximations to the roots of a real-valued function.
    14.Lucas–Lehmer primality testPrimality test for Mersenne numbers.
    15.Lenstra elliptic-curve factorizationAn algorithm for factorizing integers using elliptic curves.
    16.Goldwasser–Micali algorithmAn algorithm for the encryption of single bits.
    17.Sieve of SundaramAn algorithm to eliminate certain integers of the form i + j + 2ij where i,j ∈ N.
    18.Quadratic SieveFast, general purpose factoring algorithm; considered one of the most efficient for extracting small to medium size primes.
    19.AKS primality testDeterministically 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.