A note on probabilistically verifying integer and polynomial products
- 1 January 1989
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 36 (1), 142-149
- https://doi.org/10.1145/58562.214082
Abstract
Probabilistic algorithms are presented for testing the result of the product of two n -bit integers in O ( n ) bit operations and for testing the result of the product of two polynomials of degree n over any integral domain in 4 n + o ( n ) algebraic operations with the error probability o (l/ n 1-ε ) for any ε > 0. The last algorithm does not depend on the constants of the underlying domain.Keywords
This publication has 6 references indexed in Scilit:
- An algorithm for polynomial multiplication that does not depend on the ring constantsJournal of Algorithms, 1988
- Cyclotomic polynomials and units in cyclotomic number fieldsJournal of Number Theory, 1988
- A linear time algorithm for residue computation and a fast algorithm for division with a sparse divisorJournal of the ACM, 1987
- Fast Probabilistic Algorithms for Verification of Polynomial IdentitiesJournal of the ACM, 1980
- Resultants of cyclotomic polynomialsProceedings of the American Mathematical Society, 1970
- Approximate formulas for some functions of prime numbersIllinois Journal of Mathematics, 1962