@article{10.1145/792538.792540,
    Abstract = {We give a simple and new randomized primality testing algorithm by reducing primality testing for number n to testing if a specific univariate identity over Zn 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 Zn for any 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].},
    Address = {New York, NY, USA},
    Author = {Agrawal, Manindra and Biswas, Somenath},
    File = {Primality and Identity Testing via Chinese Remaindering - agrawal2003.pdf},
    ISSN = {0004-5411},
    Journal = {J. ACM},
    Keywords = {polynomial identity testing, Primality testing},
    Month = {jul},
    Number = {4},
    Pages = {429--443},
    Publisher = {Association for Computing Machinery},
    Title = {Primality and Identity Testing via Chinese Remaindering},
    URL = {https://doi.org/10.1145/792538.792540},
    Volume = {50},
    Year = {2003},
    bdsk-url-1 = {https://doi.org/10.1145/792538.792540},
    date-added = {2023-09-15 16:54:17 +0200},
    date-modified = {2023-09-15 16:54:17 +0200},
    file-2 = {Primality and Identity Testing via Chinese Remaindering - identity.pdf},
    issue_date = {July 2003},
    numpages = {15},
    doi = {10.1145/792538.792540}
}

@article{10.1145/792538.792540, Abstract = {We give a simple and new randomized primality testing algorithm by reducing primality testing for number n to testing if a specific univariate identity over Zn 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 Zn for any 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].}, Address = {New York, NY, USA}, Author = {Agrawal, Manindra and Biswas, Somenath}, File = {Primality and Identity Testing via Chinese Remaindering - agrawal2003.pdf}, ISSN = {0004-5411}, Journal = {J. ACM}, Keywords = {polynomial identity testing, Primality testing}, Month = {jul}, Number = {4}, Pages = {429--443}, Publisher = {Association for Computing Machinery}, Title = {Primality and Identity Testing via Chinese Remaindering}, URL = {https://doi.org/10.1145/792538.792540}, Volume = {50}, Year = {2003}, bdsk-url-1 = {https://doi.org/10.1145/792538.792540}, date-added = {2023-09-15 16:54:17 +0200}, date-modified = {2023-09-15 16:54:17 +0200}, file-2 = {Primality and Identity Testing via Chinese Remaindering - identity.pdf}, issue_date = {July 2003}, numpages = {15}, doi = {10.1145/792538.792540} }