On the effectiveness of a generalization of Miller’s primality theorem

Berrizbeitia and Olivieri showed in a recent paper that, for any integer rr, the notion of ωω-prime to base aa leads to a primality test for numbers n≡1n≡1 mod rr, that under the Extended Riemann Hypothesis (ERH) runs in polynomial time. They showed that the complexity of their test is at most the complexity of the Miller primality test (MPT), which is O((logn)4+o(1))O((logn)4+o(1)). They conjectured that their test is more effective than the MPT if rr is large.In this paper, we show that their conjecture is not true by showing that the Berrizbeitia–Olivieri primality test (BOPT) has no advantage over the MPT, either for proving primality of a prime under the ERH, or for detecting compositeness of a composite. In particular, we point out that the complexity of the BOPT depends not only on nn but also on rr and that in the worst cases (usually when nn is prime) for both tests, the BOPT is in general at least twice slower than the MPT, and in some cases (usually when nn is composite) the BOPT may be much slower. Moreover, the BOPT needs O(rlogn)O(rlogn) bit memories. We also give facts and numerical examples to show that, for some composites nn and for some rr, the rrth roots of unity ωω do not exist, and thus outputs of the BOPT are ERH conditional, whereas the MPT always quickly and definitely (without ERH) detects compositeness for all odd composites.