Fast Probabilistic Algorithms for Verification of Polynomial Identities

Fast Probabilistic Algorithms for Verification of Polynomial Identities

October 1980 | J. T. Schwartz
The paper presents fast probabilistic algorithms for testing polynomial identities and properties of systems of polynomials, building on the success of the Rabin-Strassen-Solovay primality algorithm. The algorithms are designed to be efficient and reliable, with a priori guaranteed probability of correctness. Key techniques include modular arithmetic to handle large integers and elimination theory to determine the dimension of algebraic manifolds. The methods are applied to verify polynomial identities, test for constancy and linearity, and determine divisibility relationships between polynomials. The paper also discusses the application of these techniques to the verification of theorems in elementary plane geometry, demonstrating their effectiveness in proving geometric theorems using algebraic identities.The paper presents fast probabilistic algorithms for testing polynomial identities and properties of systems of polynomials, building on the success of the Rabin-Strassen-Solovay primality algorithm. The algorithms are designed to be efficient and reliable, with a priori guaranteed probability of correctness. Key techniques include modular arithmetic to handle large integers and elimination theory to determine the dimension of algebraic manifolds. The methods are applied to verify polynomial identities, test for constancy and linearity, and determine divisibility relationships between polynomials. The paper also discusses the application of these techniques to the verification of theorems in elementary plane geometry, demonstrating their effectiveness in proving geometric theorems using algebraic identities.
Reach us at info@study.space