Fast algorithms under the extended riemann hypothesis: A concrete estimate

ABSTRACT

Several results in theoretical computer science use the following theorem: For a positive integer q, let Z-&-bull;q denote the multiplicative group of all integers x, 0-&-lt;x-&-lt;q, that are relatively prime to q. Let G be a proper subgroup of Z-&-bull;q. Then, assuming the Extended Riemann Hypothesis, there is a constant C such that if q is sufficiently large, Z-&-bull;q-&-minus;G contains a positive integer N-&-le;C (logeq)2. We show that for q-&-ge;106, one may take C-&-equil;60. As an application, we discuss a deterministic polynomial-time primality test. Miller proved that such algorithms must exist if the ERH is true, but we are unable to specify one without the concrete information given above. We eliminate this difficulty, and show how to implement a fast primality test.

REFERENCES

• 1: Lars Ahlfors, Complex Analysis, New York: McGraw-Hill (1966).
• 2: Nesmith Ankeny, The Least Quadratic Non Residue, Annals of Mathematics 55, pp. 65-72 (1952).
• 3: Andr-&-eacute; Blanchard, Initiation -&-agrave; la Th-&-eacute;orie Analytique des Nombres Premiers, Paris: Dunod (1957).
• 4: Harold Davenport, Multiplicative Number Theory, Berlin: Springer (1980).
• 5: Albert Ingham, The Distribution of Prime Numbers, New York: Stechert-Hafner (1964).
• 6: Eugene Jahnke, Fritz Emde, and Friedrich L-&-ouml;sch, Tables of Higher Functions, New York: McGraw-Hill (1960).
• 7: Gary Miller, Riemann's Hypothesis and Tests for Primality, Journal of Computer and System Sciences 13, pp. 300-317 (1976).
• 8: Hugh Montgomery, Topics in Multiplicative Number Theory, Berlin: Springer (1971).
• 9: Karl Prachar, Primzahlverteilung, Berlin: Springer (1957).
• 10: Hans Rademacher, On the Phragm-&-eacute;n-Lindel-&-ouml;f Theorem and Some Applications, Mathematische Zeitschrift 72, pp. 192-204 (1959).
• 11: Barkley Rosser and Lowell Schoenfield, Approximate Formulas for Some Functions of Prime Numbers, Illinois Journal of Mathematics 6, pp. 64-94 (1962).
• 12: Edward Titchmarsh, The Theory of Functions, Oxford: Oxford (1939).
• 13: Jacques Vélu, Tests for primality under the Riemann hypothesis, ACM SIGACT News, v.10 n.2, Summer 1978 [doi>10.1145/990524.990531]
• 14: Peter Weinberger, personal communication (1981).