Algorithms for algebraic calculations have been developed since the Antique times
- The Euclidean Algorithm for computing GCDs (Euclide, around 300 B.C.)
- The method of Erastothene for testing primality of numbers (around 200 B.C.)
- Chinese Remaindering Algorithm (Sun-Tsu, 100 A.C)
- etc.
An intense algorithmic activity for solving equations since the Renaissance
- Descates Rule for isolating real roots of univariate polynomials (Descartes 1596 - 1650)
- The complexity analysis of the Eucliddean Algorithm by Lamé (1845)
- Newton iteration for solving equations (1669)
- Galois Theory for deciding when univariate equations can be solved by radicals [Esc01]
- First algorithm for factoring univariate polynomials by Kronecker [Kro97b,Kro97a]
- The method of Gauss for multiplying complex numbers, see also Karatsuba's trick [KO63].
- etc.
The discovery of fast algorithms since the introduction of computers
- Karatsuba's trick for univariate polynomial multiplication [KO63],
- FFT-based univariate polynomial multiplication (Cooley and Tukey, 1965),
- First algorithm and its implementation of polynomial system solver [Buc65]
- Strassen's method for matrix multiplication [Str69]
- First efficient algorithm for factoring polynomials [Ber67,Zas69,LHWLL82]
- Fast algorithm for division (Cook, 1966) (Sieveking, 1972)
- Fast Chinese Remaindering Algorithm (Borodin & Moenck)
- Fast algorithms for GCD computations (Knuth, 1970), (Schönage, 1971) and others
Marc Moreno Maza
2008-01-07