Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Some heuristics and results for small cycles of the discrete logarithm

Authors: Joshua Holden and Pieter Moree
Journal: Math. Comp. 75 (2006), 419-449
MSC (2000): Primary 11A07; Secondary 11N37, 94A60, 11-04
Published electronically: June 28, 2005
MathSciNet review: 2176407
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Brizolis asked the question: does every prime $p$ have a pair $(g,h)$such that $h$ is a fixed point for the discrete logarithm with base $g$? The first author previously extended this question to ask about not only fixed points but also two-cycles, and gave heuristics (building on work of Zhang, Cobeli, Zaharescu, Campbell, and Pomerance) for estimating the number of such pairs given certain conditions on $g$ and $h$. In this paper we extend these heuristics and prove results for some of them, building again on the aforementioned work. We also make some new conjectures and prove some average versions of the results.

References [Enhancements On Off] (What's this?)

  • 1. Campbell, Mariana, On fixed points for discrete logarithms, Master's Thesis, 2003.
  • 2. Cristian Cobeli and Alexandru Zaharescu, An exponential congruence with solutions in primitive roots, Rev. Roumaine Math. Pures Appl. 44 (1999), 15-22. MR 1841958 (2002d:11005)
  • 3. Carl-Gustav Esseen, A stochastic model for primitive roots, Rev. Roumaine Math. Pures Appl. 38 (1993), 481-501.MR 1258051 (94m:11110)
  • 4. Étienne Fouvry, Théorème de Brun-Titchmarsh: Application au théorème de Fermat, Invent. Math. 79 (1985), 383-407. MR 0778134 (86g:11052)
  • 5. Richard K. Guy, Unsolved problems in number theory, Springer-Verlag, 1981.MR 0656313 (83k:10002)
  • 6. Joshua Holden, Fixed points and two-cycles of the discrete logarithm, Algorithmic number theory (ANTS 2002) (C. Fieker and D. Kohel, eds.) LNCS, Springer, 2002, pp. 405-415. MR 2041100
  • 7. -, Addenda/corrigenda: Fixed points and two-cycles of the discrete logarithm, 2002, unpublished
  • 8. Mark Kac, Statistical independence in probability, analysis and number theory, The Carus Mathematical Monographs, vol. 12, Mathematical Association of America, 1959. MR 0110114 (22:996)
  • 9. Pieter Moree and Peter Stevenhagen, A two-variable Artin conjecture, J. Number Theory 85 (2000), 291-304. MR 1802718 (2001k:11188)
  • 10. -, Prime divisors of the Lagarias sequence, J. Théor. Nombres Bordeaux 13 (2001), 241-251. MR 1838084 (2002c:11016)
  • 11. Pieter Moree, Approximation of singular series and automata, Manuscripta Math. 101 (2000), 385-399. MR 1751040 (2001f:11204)
  • 12. -, Asymptotically exact heuristics for (near) primitive roots, J. Number Theory 83 (2000), 155-181. MR 1767657 (2001m:11161)
  • 13. Pieter Moree, An exponential congruence with solutions in primitive roots (review), Mathematical Reviews (2002). MR 1841958 (2002d:11005)
  • 14. Carl Pomerance, Personal communication.
  • 15. Karl Prachar, Primzahlverteilung, Springer, 1957.MR 0087685 (19:393b)
  • 16. P.J. Stephens, An average result for Artin's conjecture, Mathematika 16 (1969), 178-188. MR 0498449 (58:16565)
  • 17. -, Prime divisors of second order linear recurrences I, II, J. Number Theory 8 (1976), 313-332, 333-345.MR 0417081 (54:5142); MR 0417082 (54:5143)
  • 18. Wen Peng Zhang, On a problem of Brizolis, Pure Appl. Math. 11 (1995), 1-3. MR 1454053 (98d:11099)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11A07, 11N37, 94A60, 11-04

Retrieve articles in all journals with MSC (2000): 11A07, 11N37, 94A60, 11-04

Additional Information

Joshua Holden
Affiliation: Department of Mathematics, Rose-Hulman Institute of Technology, Terre Haute, Indiana, 47803-3999

Pieter Moree
Affiliation: Max-Planck-Institut für Mathematik, Vivatsgasse 7, D-53111 Bonn, Germany

Received by editor(s): January 4, 2004
Received by editor(s) in revised form: August 30, 2004
Published electronically: June 28, 2005
Additional Notes: The first author would like to thank the Rose-Hulman Institute of Technology for the special stipend which supported this project during the summer of 2002
The research of the second author was carried out while he was a visiting assistant professor at the University of Amsterdam and supported by Prof. E. M. Opdam’s Pioneer Grant of the Netherlands Organization for Scientific Research (NWO)
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society