Elementary algebra revisited: Randomized algorithms
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.