[Zhang
2010] *On the effectiveness of a generalization of Miller's
primality theorem, *Journal of Complexity, **26**:2 (2010), 200-208.

**A****BSTRACT**. Berrizbeitia
and Olivieri showed in a recent paper that, for any
integer* r*, the notion of *ω*-prime to base *a* leads to a primality test for numbers *n* ≡ 1 mod *r*, 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*((log *n*)^{4+o(1)}). They conjectured that their test is more effective than the MPT
if *r* 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 *n* but also on* r *and that in the worst cases (usually
when *n* is prime) for both tests, the BOPT is in general at least twice
slower than the MPT, and in some cases (usually when* n* is composite) the BOPT may be much
slower. Moreover, the BOPT needs *O*(*r** *log *n*) bit
memories. We also give facts and numerical examples to show that, for some
composites* n* and for some *r*, the *r* th 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.