Mathematical means either useful for Mathematics or based on Mathematics.

I guess one has to include the following items:

(1) Euclid and LLL

(2) Newton and variations based on the existence of attracting fixpoints for maps.

(3) Algorithms for linear algebra and, in particular, FFT

(4) Simplex algorithm and other algorithms using convexity properties

(5) Quadrature formula (integration, differential equations etc.)

(6) Factorization (integers, polynomials etc.) and primality proving

(7) Algorithms for computations with Groebner bases.

(8) Sorting and searching

(9) WZ and similar algorithms yielding automated proofs

This list is surely a strict subset of a satisfying answer. Which important (classes of) algorithms are missing? (I guess there must be also be something in probability and perhaps in geometry.)

Let me also specify that I would like the list to contain general-purpose algorithms, not algorithms for specific tasks, like encryption, error-correction, computations of class numbers for number fields etc. I guess, algorithms for elliptic curves are on the boundary and perhaps already slightly outside the list (many of them are however used for integer-factorization and are thus implicitely contained in item (6) of the previous list).

A last question: Are we missing important fundamental algorithms? (This is of course tricky, since we are probably not aware of their potential usefulness). By this I do not mean a algorithm for factorizing integers in polynomial time or an (impossible) algorithm deciding the existence of solutions for arbitrary Diophantine equations but algorithms useful for a large class of problems for which we have presently only case by case tricks.ge