Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Statistical evidence for small generating sets


Authors: Eric Bach and Lorenz Huelsbergen
Journal: Math. Comp. 61 (1993), 69-82
MSC: Primary 11N69
DOI: https://doi.org/10.1090/S0025-5718-1993-1195432-5
MathSciNet review: 1195432
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

$\displaystyle 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

$\displaystyle (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 [Enhancements On Off] (What's this?)

  • [1] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355-380. MR 1023756 (91m:11096)
  • [2] R. Baillie and S. S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), 1391-1417. MR 583518 (81j:10005)
  • [3] Z. I. Borevich and I. R. Shafarevich, Number theory, Academic Press, New York, 1966. MR 0195803 (33:4001)
  • [4] H. Brown and H. Zassenhaus, Some empirical observations on primitive roots, J. Number Theory 3 (1971), 306-309. MR 0288072 (44:5270)
  • [5] D. A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. (3) 12 (1962), 179-192. MR 0132732 (24:A2569)
  • [6] H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statist. 23 (1952), 493-507. MR 0057518 (15:241c)
  • [7] H. Cohn, A classical invitation to algebraic numbers and class fields. Springer-Verlag, New York, 1978. MR 506156 (80c:12001)
  • [8] H. Davenport, Multiplicative number theory, Springer-Verlag, New York, 1980. MR 606931 (82m:10001)
  • [9] R. E. Dressier, A property of the $ \varphi $ and $ {\sigma _j}$ functions, Compositio Math. 31 (1975), 115-118. MR 0392792 (52:13605)
  • [10] P. D. T. A. Elliott, The distribution of primitive roots, Canad. J. Math. 21 (1969), 822-841. MR 0246835 (40:104)
  • [11] -, A problem of Erdős concerning power residue sums, Acta Arith. 13 (1967), 131-149; Corrigendum, ibid. 14 (1968), 437. MR 0220689 (36:3741)
  • [12] P. Erdős and M. Kac, On the Gaussian law of errors in the theory of additive number theoretic functions, Amer. J. Math. 62 (1940), 738-742. MR 0002374 (2:42c)
  • [13] 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.
  • [14] W. Feller, Introduction to probability theory and its applications, Wiley, New York, 1968. MR 0228020 (37:3604)
  • [15] S. Graham and C. J. Ringrose, Lower bounds for least quadratic nonresidues, Analytic Number Theory: Proceedings of a Conference in Honor of Paul T. Bateman (B. C. Berndt et al., eds.), Birkhäuser, Boston, 1990, pp. 269-309. MR 1084186 (92d:11108)
  • [16] E. J. Gumbel, Statistics of extremes, Columbia Univ. Press, New York, 1958. MR 0096342 (20:2826)
  • [17] H. Halberstam, On the distribution of additive number theoretic functions. III, J. London Math. Soc. 31 (1956), 14-27. MR 0073627 (17:461e)
  • [18] R. Heath-Brown, Artin's conjecture for primitive roots, Quart. J. Math. Oxford Ser. (2) 37 (1986), 27-38. MR 830627 (88a:11004)
  • [19] C. Hooley, On Artin's conjecture, J. Reine Angew. Math. 225 (1967), 209-220. MR 0207630 (34:7445)
  • [20] J. L. Hafner and K. S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 4 (1989), 837-850. MR 1002631 (91f:11090)
  • [21] 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 (80c:10045)
  • [22] J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic Number Fields (A. Fröhlich, ed.), Academic Press, London, 1977, pp. 409-464. MR 0447191 (56:5506)
  • [23] D. H. Lehmer and E. Lehmer, Heuristics, anyone? Studies in Mathematical Analysis and Related Topics (G. Szegö, ed.), Stanford Univ. Press, Stanford, CA, 1962, pp. 202-210. MR 0144868 (26:2409)
  • [24] D. H. Lehmer, E. Lehmer, and D. Shanks, Integer sequences with prescribed quadratic character, Math. Comp. 24 (1970), 433-451. MR 0271006 (42:5889)
  • [25] K. S. McCurley, The least r-free number in an arithmetic progression, Trans. Amer. Math. Soc. 293 (1986), 467-475. MR 816304 (87b:11016)
  • [26] G. L. Miller, Riemann's hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), 300-317. MR 0480295 (58:470a)
  • [27] A. W. Marshall and I. Olkin, Inequalities: theory of majorization and its applications, Academic Press, New York, 1979. MR 552278 (81b:00002)
  • [28] H. L. Montgomery, Multiplicative number theory, Lecture Notes in Math., vol. 227, Springer-Verlag, New York, 1971. MR 1790423 (2001f:11001)
  • [29] M. O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), 128-138. MR 566880 (81f:10003)
  • [30] J. B. Rosser, The nth prime is greater than $ n\log n$, Proc. London Math. Soc. 45 (1939), 21-44.
  • [31] J. Sorenson and I. Parberry, Two fast parallel prime number sieves, Technical Report CRPDC-91-8, Center for Research in Parallel and Distributed Computing, University of North Texas, July 1991; Inform. Comput. (to appear). MR 1294306 (95h:11097)
  • [32] A. J. Stephens and H. C. Williams, An open architecture number sieve, Number Theory and Cryptography (J. H. Loxton, ed.), Cambridge Univ. Press, Cambridge, 1990, pp. 38-75. MR 1055399
  • [33] G. Tonelli, Bemerkung über die Auflösung quadratischer Congruenzen, Gött. Nachr. (1891), 344-346.
  • [34] D. Suryanarayana, On $ \Delta (x,n) = \varphi (x,n) - x\varphi (n)/n$ , Proc. Amer. Math. Soc. 44 (1974), 17-21. MR 0332636 (48:10962)
  • [35] S. Wagon, The evidence: primality testing, Math. Intelligencer 8 (1986), 58-61. MR 846996 (87m:11124)
  • [36] S. S. Wagstaff, Jr., Greatest of the least primes in arithmetic progressions having a given modulus, Math. Comp. 33 (1979), 1073-1080. MR 528061 (81e:10038)
  • [37] A. E. Western and J. C. P. Miller, Tables of indices and primitive roots, Cambridge Univ. Press, Cambridge, 1968. MR 0246488 (39:7792)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11N69

Retrieve articles in all journals with MSC: 11N69


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1993-1195432-5
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society