A note on probabilistically verifying integer and polynomial products

DOI10.1145/58562.214082MaRDI QIDQ3477964zbMATH OpenOpenAlexFDO

Authors Michael Kaminski

Publication date 1989

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/58562.214082

zbMATH Keywords

cyclotomiccomplexitypolynomialsprobabilistic algorithmspolynomial multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
• Probabilistic absolute irreducibility test for polynomials
• A probabilistic algorithm for verifying polynomial middle product in linear time
• scientific article; zbMATH DE number 2079409
• Primality and identity testing via Chinese remaindering

Cited in

(7)

• Polynomial modular product verification and its implications
• Self-testing/correcting with applications to numerical problems
• scientific article; zbMATH DE number 2148626 (Why is no real title available?)
• A survey on delegated computation
• A probabilistic algorithm for verifying polynomial middle product in linear time
• A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
• Updateable Inner Product Argument with Logarithmic Verifier and Applications

This page was built for publication: A note on probabilistically verifying integer and polynomial products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3477964)