Access Restriction

Author Agrawal, Manindra ♦ Biswas, Somenath
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2003
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Primality testing ♦ Polynomial identity testing
Abstract We give a simple and new randomized primality testing algorithm by reducing primality testing for number $\textit{n}$ to testing if a specific univariate identity over $Z_{n}$ holds.We also give new randomized algorithms for testing if a multivariate polynomial, over a finite field or over rationals, is identically zero. The first of these algorithms also works over $Z_{n}$ for any $\textit{n}.$ The running time of the algorithms is polynomial in the size of arithmetic circuit representing the input polynomial and the error parameter. These algorithms use fewer random bits and work for a larger class of polynomials than all the previously known methods, for example, the Schwartz--Zippel test [Schwartz 1980; Zippel 1979], Chen--Kao and Lewin--Vadhan tests [Chen and Kao 1997; Lewin and Vadhan 1998].
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 2003-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 50
Issue Number 4
Page Count 15
Starting Page 429
Ending Page 443

Open content in new tab

   Open content in new tab
Source: ACM Digital Library