Algebra
- Buchberger's algorithm. Finds a Gräbner basis.
- Extended Euclidean algorithm. Solves the equation ax+by= c.
- Fourier transform multiplication. For very big numbers, computing the fast Fourier transforms for two numbers, and multiplying the two results entry by entry.
- Gram-Schmidt process. Orthogonalizes a set of vectors.
- Gauss-Jordan elimination. Solves systems of linear equations.
- Karatsuba multiplication. Recursive algorithm efficient for big numbers. Derived from the Toom-Cook method.
- Knuth-Bendix completion. For rewriting rule systems.
- Multivariate division. For polynomials in several indeterminates.
- Risch algorithm. Translates indefinite integral to algebraic problem.
- Toom-Cook (Toom3). Splits each number to be multiplied into multiple parts.
Eigenvalue algorithm
Algorithms to find the Eigenvalue and/or Eigenvector of a matrix.- QR algorithm. A popular method based on the QR decomposition.
- Inverse iteration. Iterative eigenvalue algorithm.
- Rayleigh quotient iteration. Extends the principle of the inverse iteration by using the Rayleigh quotient to obtain increasingly accurate eigenvalue estimates.
- Arnoldi iteration. Compute the eigenvalues of the orthogonal projection of A onto the Krylov subspace.
- Lanczos iteration. Method to find a zero vector in the process of the quadratic sieve.
- Jacobi method. Numerical procedure for the calculation of all eigenvalues and eigenvectors of a real symmetric. matrix
- Bisection.
- Divide-and-conquer. Apply to real symmetric matrices.
- Richardson eigenvector algorithm.
- Max-Plus. Eigenvector algorithm for nonlinear H 1 control.
- Abrams and Lloyd eigenvector algorithm.
Arithmetic
- Binary GCD algorithm. Efficient way of calculating greatest common divisor.
- Booth's multiplication. Multiply two signed numbers in two's complement notation.
- Euclidean algorithm. Computes the greatest common divisor.
- Binary multiplication (Peasant or Egyptian multiplication). Decomposes the larger multiplicand into a sum of powers of two and creates a table of doublings of the second multiplicand.
Discrete logarithm in group theory
- Baby-step giant-step. This is a series of well defined steps to compute the discrete logarithm.
- Pollard's rho algorithm for logarithms. Analogous to Pollard's rho algorithm for integer factorization but solves the discrete logarithm problem.
- Pohlig-Hellman algorithm. Solves the problem for a multiplicative group whose order is a smooth integer. Based on the Chinese remainder theorem and runs in polynomial time.
- Index calculus algorithm. Best known algorithm for certain groups, as the multiplicative group modulo m.
Integer factorization
Breaking an integer into its prime factors . Also named prime factorization.- Fermat's factorization method. A representation of an odd integer as the difference of two squares.
- Trial division. The simplest of the integer factorization algorithms. Try to divide the integer n by every prime number.
- Lenstra elliptic curve factorization or elliptic curve factorization method (ECM). Fast, sub-exponential running time, employs elliptic curves.
- Pollard's rho . Variation of Pollard's p-1 that is effective at splitting composite numbers with small factors.
- Pollard's p-1. A special-purpose algorithm, that is only suitable for integers with specific types of factors.
- Congruence of squares. Finding a congruence of squares modulo n is a mean to to factor the integer n.
- Quadratic sieve. Uses the idea of Dixon's method. It is a general-purpose algorithm that is simpler than the number field sieve and the fastest for integers under 100 decimal digits.
- Dixon's factorization method. General-purpose integer factorization algorithm.
- Special number field sieve. Special-purpose algorithm ideal for Fermat numbers.
- General number field sieve (GNS). Derived from special number field sieve. Efficient algorithm known for factoring big integers. Uses steps to factor the integer.
Prime test
Determining whether a given number is prime.- AKS primality test (Agrawal-Kayal-Saxena). The first published algorithm to be simultaneously polynomial, deterministic, and unconditional. Generalization of Fermat's theorem, extended to polynomials.
- Fermat primality test. Rely on an equality or set of equalities that hold true for prime values, and then see whether or not they hold for the number to test.
- Miller-Rabin primality test. Similar to the Fermat primality test. Unconditional probabilistic algorithm.
- Sieve of Eratosthenes. Ancient algorithm for finding all prime numbers up to a specified integer.
- Sieve of Atkin. Optimized version of the sieve of Eratosthenes.
- Solovay-Strassen primality test. Same principle as the Fermat test.
Numerical
- Fibonacci. Calculating the sequence of Fibonacci.
- Biconjugate gradient method. Solves systems of linear equations.
- Dancing Links. Finds all solutions to the exact cover problem.
- De Boor algorithm. Computes splines.
- De Casteljau's algorithm. Computes Bezier curves.
- False position method. Approximates roots of a function.
- Gauss-Legendre. Computes the digits of pi.
- Kahan summation. A more accurate method of summing floating-point numbers.
- MISER. Monte Carlo simulation, numerical integration.
- Newton's method. Finds zeros of functions with calculus.
- Rounding functions. The classic ways to round numbers.
- Secant method. Approximates roots of a function.
- Shifting nth-root. Digit by digit root extraction.
- Square root. Approximates the square root of a number.
- Borwein's algorithm. Calculates the value of 1/e.
- Metropolis-Hastings. Generate a sequence of samples from the probability distribution of one or more variables.