We examine a primality testing algorithm and show that this test is stronger than some of the most popular tests. From this, we show the correctness of the algorithm based on a widely believed conjecture. 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.

The full report is available in PostScript.

Towards a deterministic polynomial-time Primality Test