On the effectiveness of a generalization of Miller’s primality theorem
Authors:
Zhenxiang Zhang
Affiliation:
Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, People’s Republic of China
Abstract:
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((logn)4+o(1)). They conjectured that their test is more effective than the MPT if r is large.