Elementary algebra revisited: Randomized algorithms
Gene D. Cooperman, George Havas · DIMACS series in discrete mathematics and theoretical computer science · 1998
We look at some simple algorithms for elementary problems in algebra that yield dramatic efficiency improvements over standard methods through randomization.The randomized algorithms are, in a sense, "obvious".Their formal statement was delayed partly by the need for rigorous analysis, but more so by the need to re-think traditional approaches to elementary algorithms.We illustrate this philosophy with some basic problems in computational number theory (GCD of many integers), linear algebra (low-rank Gaussian elimination) and group theory (random subproducts for subgroup construction), along with a brief survey of other areas.