Riemann's Hypothesis and tests for primality

摘要

The purpose of this paper is to present new upper bounds on the complexity of algorithms for testing the primality of a number. The first upper bound is 0(n&frac17;); it improves the previously best known bound of 0(n¼) due to Pollard [11].

The second upper bound is dependent on the Extended Riemann Hypothesis (ERH): assuming ERH, we produce an algorithm which tests primality and runs in time 0((log n)4) steps. Thus we show that primality is testable in time a polynomial in the length of the binary representation of a number.

Finally, we give a partial solution to the relationship between the complexity of computing the prime factorization of a number, computing the Euler phi function, and computing other related functions.