Riemann's hypothesis and tests for primality

摘要

In this paper we present two algorithms for testing primality of an integer. The first algorithm runs in 0(n1/7) steps; while, the second runs in 0(log4n) step but assumes the Extended Riemann Hypothesis. We also show that a class of functions which includes the Euler phi function are computationally equivalent to factoring integers.