Towards a deterministic polynomial-time Primality Test
Neeraj Kayal(98226) and Nitin Saxena (98247), April,
2002
We examine a primality testing algorithm presented in
Primality and Identity Testing via Chinese Remaindering: FOCS 1999
and the related conjecture in
Prashant and Rajat: BTP-report 2001.
We show that this test is stronger than
some of the most popular tests: the Fermat test, the Solovay Strassen test
and a strong form of the Fibonacci test. From this, we show the correctness
of the algorithm based on a widely believed conjecture, the Extended Riemann
Hypothesis. We also show that any n which is accepted by the algorithm must
be an odd square-free number. Thus, it is arguably the simplest and yet the
strongest test for primality.
Based on our computations and results proved in this paper we feel that
unlike other tests, this test is very promising as the related conjecture
seems provable.
Full Report (PS-gzipped: 120K)
Conjectures & Experimental Data
Back to the list of BTP reports