Published in

Association for Computing Machinery (ACM), Journal of the ACM, 4(27), p. 701-717, 1980

DOI: 10.1145/322217.322225

Springer, Lecture Notes in Computer Science, p. 200-215, 1979

DOI: 10.1007/3-540-09519-5_72

Links

Tools

Export citation

Search in Google Scholar

Fast Probabilistic Algorithms for Verification of Polynomial Identities.

Journal article published in 1980 by Jacob T. Schwartz
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

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.