Association for Computing Machinery (ACM), Journal of the ACM, 4(27), p. 701-717, 1980
Springer, Lecture Notes in Computer Science, p. 200-215, 1979
Full text: Download
The startling success of the Rabin-Strassen-Solovay primality algorithm, togehter with the intriguing foundational possibility that axioms of randomness may constitute a useful fundamental source of mathematical truth independent of the standard axiomatic structure of mathematics, suggests a vigorous search for probabilistic algorithms. In illustration of this observation, we present various fast probabilistic algorithms, with probability of correctness guaranteed a priori, for testing polynomial identities and properties of systems of polynomials. Ancillary fast algorithms for calculating resultants and Sturm sequences are given. Theorems of elementary geometry can be proved much more efficiently by the techniques presented than by any known artificial intelligence approach.