### A note on probabilistically verifying integer and polynomial productsA note on probabilistically verifying integer and polynomial products

Access Restriction
Subscribed

 Author Kaminski, Michael Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1989 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Probabilistic algorithms are presented for testing the result of the product of two $\textit{n}-bit$ integers in $\textit{O}(\textit{n})$ bit operations and for testing the result of the product of two polynomials of degree $\textit{n}$ over $\textit{any}$ integral domain in $4\textit{n}$ + $\textit{o}(\textit{n})$ algebraic operations with the error probability $\textit{o}(l/\textit{n}1-ε)$ for any ε > 0. The last algorithm does not depend on the constants of the underlying domain. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1989-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 36 Issue Number 1 Page Count 8 Starting Page 142 Ending Page 149

#### Open content in new tab

Source: ACM Digital Library