首页 | 本学科首页   官方微博 | 高级检索  
     


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 rr, the notion of ωω-prime to base aa leads to a primality test for numbers n≡1n1 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.
Keywords:Strong probable prime (sprp) tests   The Miller primality test   The Berrizbeitia&ndash  Olivieri primality test   Primality proving under the ERH   Compositeness detecting   Complexity analysis
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号