Statistical evidence for small generating sets
HTML articles powered by AMS MathViewer
- by Eric Bach and Lorenz Huelsbergen PDF
- Math. Comp. 61 (1993), 69-82 Request permission
Abstract:
For an integer n, let $G(n)$ denote the smallest x such that the primes $\leq x$ generate the multiplicative group modulo n. We offer heuristic arguments and numerical data supporting the idea that \[ G(n) \leq {(\log 2)^{ - 1}}\log n\log \log n\] asymptotically. We believe that the coefficient $1/\log 2$ is optimal. Finally, we show the average value of $G(n)$ for $n \leq N$ is at least \[ (1 + o(1))\log \log N\log \log \log N,\] and give a heuristic argument that this is also an upper bound. This work gives additional evidence, independent of the ERH, that primality testing can be done in deterministic polynomial time; if our bound on $G(n)$ is correct, there is a deterministic primality test using $O{(\log n)^2}$ multiplications modulo n.References
- Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355â380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
- Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391â1417. MR 583518, DOI 10.1090/S0025-5718-1980-0583518-6
- A. I. Borevich and I. R. Shafarevich, Number theory, Pure and Applied Mathematics, Vol. 20, Academic Press, New York-London, 1966. Translated from the Russian by Newcomb Greenleaf. MR 0195803
- H. Brown and H. Zassenhaus, Some empirical observations on primitive roots, J. Number Theory 3 (1971), 306â309. MR 288072, DOI 10.1016/0022-314X(71)90004-7
- D. A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. (3) 12 (1962), 179â192. MR 132732, DOI 10.1112/plms/s3-12.1.179
- Herman Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics 23 (1952), 493â507. MR 57518, DOI 10.1214/aoms/1177729330
- Harvey Cohn, A classical invitation to algebraic numbers and class fields, Universitext, Springer-Verlag, New York-Heidelberg, 1978. With two appendices by Olga Taussky: âArtinâs 1932 Göttingen lectures on class field theoryâ and âConnections between algebraic number theory and integral matricesâ. MR 506156
- Harold Davenport, Multiplicative number theory, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. MR 606931
- Robert E. Dressler, A property of the $\varphi$ and $\sigma _{j}$ functions, Compositio Math. 31 (1975), no. 2, 115â118. MR 392792
- P. D. T. A. Elliott, The distribution of primitive roots, Canadian J. Math. 21 (1969), 822â841. MR 246835, DOI 10.4153/CJM-1969-092-6
- P. D. T. A. Elliott, A problem of ErdĆs concerning power residue sums, Acta Arith. 13 (1967/68), 131â149. MR 220689, DOI 10.4064/aa-13-2-131-149
- P. Erdös and M. Kac, The Gaussian law of errors in the theory of additive number theoretic functions, Amer. J. Math. 62 (1940), 738â742. MR 2374, DOI 10.2307/2371483 P. ErdĆs and A. RĂ©nyi, On a classical problem of probability theory, MTA Mat. Kut. Int. Közl. 6A (1961), 215-220. Reprinted in Selected papers of AlfrĂ©d RĂ©nyi, vol. 2, Akademiai Kiado, Budapest, 1976, pp. 617-621.
- William Feller, An introduction to probability theory and its applications. Vol. I, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020
- S. W. Graham and C. J. Ringrose, Lower bounds for least quadratic nonresidues, Analytic number theory (Allerton Park, IL, 1989) Progr. Math., vol. 85, BirkhĂ€user Boston, Boston, MA, 1990, pp. 269â309. MR 1084186
- E. J. Gumbel, Statistics of extremes, Columbia University Press, New York, 1958. MR 0096342
- H. Halberstam, On the distribution of additive number-theoretic functions. III, J. London Math. Soc. 31 (1956), 14â27. MR 73627, DOI 10.1112/jlms/s1-31.1.14
- D. R. Heath-Brown, Artinâs conjecture for primitive roots, Quart. J. Math. Oxford Ser. (2) 37 (1986), no. 145, 27â38. MR 830627, DOI 10.1093/qmath/37.1.27
- Christopher Hooley, On Artinâs conjecture, J. Reine Angew. Math. 225 (1967), 209â220. MR 207630, DOI 10.1515/crll.1967.225.209
- James L. Hafner and Kevin S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, 837â850. MR 1002631, DOI 10.1090/S0894-0347-1989-1002631-0
- G. Kolesnik and E. G. Straus, On the first occurrence of values of a character, Trans. Amer. Math. Soc. 246 (1978), 385â394. MR 515545, DOI 10.1090/S0002-9947-1978-0515545-6
- J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409â464. MR 0447191
- D. H. Lehmer and Emma Lehmer, Heuristics, anyone?, Studies in mathematical analysis and related topics, Stanford Univ. Press, Stanford, Calif., 1962, pp. 202â210. MR 0144868
- D. H. Lehmer, Emma Lehmer, and Daniel Shanks, Integer sequences having prescribed quadratic character, Math. Comp. 24 (1970), 433â451. MR 271006, DOI 10.1090/S0025-5718-1970-0271006-X
- Kevin S. McCurley, The least $r$-free number in an arithmetic progression, Trans. Amer. Math. Soc. 293 (1986), no. 2, 467â475. MR 816304, DOI 10.1090/S0002-9947-1986-0816304-1
- Gary L. Miller, Riemannâs hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300â317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
- Albert W. Marshall and Ingram Olkin, Inequalities: theory of majorization and its applications, Mathematics in Science and Engineering, vol. 143, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. MR 552278
- Harold Davenport, Multiplicative number theory, 3rd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York, 2000. Revised and with a preface by Hugh L. Montgomery. MR 1790423
- Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128â138. MR 566880, DOI 10.1016/0022-314X(80)90084-0 J. B. Rosser, The nth prime is greater than $n\log n$, Proc. London Math. Soc. 45 (1939), 21-44.
- Jonathan Sorenson and Ian Parberry, Two fast parallel prime number sieves, Inform. and Comput. 114 (1994), no. 1, 115â130. MR 1294306, DOI 10.1006/inco.1994.1082
- A. J. Stephens and H. C. Williams, An open architecture number sieve, Number theory and cryptography (Sydney, 1989) London Math. Soc. Lecture Note Ser., vol. 154, Cambridge Univ. Press, Cambridge, 1990, pp. 38â75. MR 1055399 G. Tonelli, Bemerkung ĂŒber die Auflösung quadratischer Congruenzen, Gött. Nachr. (1891), 344-346.
- D. Suryanarayana, On $\Delta (x,\,n)=\phi (x,\,n)$ $-x\phi (n)/n$, Proc. Amer. Math. Soc. 44 (1974), 17â21. MR 332636, DOI 10.1090/S0002-9939-1974-0332636-5
- Stan Wagon, Primality testing, Math. Intelligencer 8 (1986), no. 3, 58â61. MR 846996, DOI 10.1007/BF03025793
- Samuel S. Wagstaff Jr., Greatest of the least primes in arithmetic progressions having a given modulus, Math. Comp. 33 (1979), no. 147, 1073â1080. MR 528061, DOI 10.1090/S0025-5718-1979-0528061-7
- A. E. Western and J. C. P. Miller, Tables of indices and primitive roots, Royal Society Mathematical Tables, Vol. 9, Published for the Royal Society at the Cambridge University Press, London 1968. MR 0246488
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 61 (1993), 69-82
- MSC: Primary 11N69
- DOI: https://doi.org/10.1090/S0025-5718-1993-1195432-5
- MathSciNet review: 1195432