Riemann's Hypothesis and tests for primality

ABSTRACT

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.

REFERENCES

• 1: N.C. Ankeny, "The Least Quadratic Non-Residue," Annals of mathematics 55 (1952) 65-72.
• 2: D.A. Burgess, "The Distribution of Quadratic Residues and Non-Residues," Mathematika 4 (1957) 106-112.
• 3: D.A. Burgess, "On Character Sums and Primitive Roots," Proc. London Math. Soc. (3) 12 (1962) 179-192.
• 4: D.A. Burgess, "On Character Sums and L-series," Proc. London Math. Soc. (3) 12 (1962) 193-206.
• 5: R.D. Carmichael, "On Composite Numbers p Which Satisfy the Fermat Congruence ap−1&Xgr;p," American Math. Monthly 19 (1912) 22-27.
• 6: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 7: H. Davenport and P. Erdös, "The Distribution of Quadratic and Higher Residues," Publ. Math. Debreien 2 (1952) 252-265.
• 8: R. Karp, "Reducibility Among Combinatorial Problems," |Complexity of Computer Computations,# R.E. Miller and J.W. Thatcher, eds., Plenum Press, New York (1972) 85-103.
• 9: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 10: H. Montgomery, Topics in Multiplicative Number Theory, Springer-Verlag Lecture Notes #227, 120.
• 11: J. Pollard, "An Algorithm for Testing the Primality of Any Integer," Bull. London Math. Soc. 3 (1971) 337-340.
• 12: A. Selberg, "Contributions to the Theory of Dirichlet L Functions," Avhandlinger utgett av Det Norske Videnskops, Akademi i Oslo (1934).
• 13: D. Shanks, "Class Number, A Theory of Factorization, and Genera," Proceedings of Symposia in Pure Mathematics (20), 1969 Number Theory Institute, AMS (1971) 415-440.
• 14: A. Shönhage and V. Strassen, "Schnelle Multiplikation Grosser Zahlen," Computing 7 (1971) 281-292.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Theory