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 Free Access

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), no. 1, 15–22. MR 1841958
  • 3. Carl-Gustav Esseen, A stochastic model for primitive roots, Rev. Roumaine Math. Pures Appl. 38 (1993), no. 6, 481–501. MR 1258051
  • 4. Étienne Fouvry, Théorème de Brun-Titchmarsh: application au théorème de Fermat, Invent. Math. 79 (1985), no. 2, 383–407 (French). MR 778134, 10.1007/BF01388980
  • 5. Richard K. Guy, Unsolved problems in number theory, Unsolved Problems in Intuitive Mathematics, vol. 1, Springer-Verlag, New York-Berlin, 1981. Problem Books in Mathematics. MR 656313
  • 6. Joshua Holden, Fixed points and two-cycles of the discrete logarithm, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 405–415. MR 2041100, 10.1007/3-540-45455-1_32
  • 7. -, Addenda/corrigenda: Fixed points and two-cycles of the discrete logarithm, 2002, unpublished http://xxx.lanl.gov/abs/math.NT/0208028
  • 8. Mark Kac, Statistical independence in probability, analysis and number theory., The Carus Mathematical Monographs, No. 12, Published by the Mathematical Association of America. Distributed by John Wiley and Sons, Inc., New York, 1959. MR 0110114
  • 9. Pieter Moree and Peter Stevenhagen, A two-variable Artin conjecture, J. Number Theory 85 (2000), no. 2, 291–304. MR 1802718, 10.1006/jnth.2000.2547
  • 10. Pieter Moree and Peter Stevenhagen, Prime divisors of the Lagarias sequence, J. Théor. Nombres Bordeaux 13 (2001), no. 1, 241–251 (English, with English and French summaries). 21st Journées Arithmétiques (Rome, 2001). MR 1838084
  • 11. Pieter Moree, Approximation of singular series and automata, Manuscripta Math. 101 (2000), no. 3, 385–399. With an appendix by Gerhard Niklasch. MR 1751040, 10.1007/s002290050222
  • 12. Pieter Moree, Asymptotically exact heuristics for (near) primitive roots, J. Number Theory 83 (2000), no. 1, 155–181. MR 1767657, 10.1006/jnth.1999.2502
  • 13. Cristian Cobeli and Alexandru Zaharescu, An exponential congruence with solutions in primitive roots, Rev. Roumaine Math. Pures Appl. 44 (1999), no. 1, 15–22. MR 1841958
  • 14. Carl Pomerance, Personal communication.
  • 15. Karl Prachar, Primzahlverteilung, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957 (German). MR 0087685
  • 16. P. J. Stephens, An average result for Artin’s conjecture, Mathematika 16 (1969), 178–188. MR 0498449
  • 17. P. J. Stephens, Prime divisors of second-order linear recurrences. I, J. Number Theory 8 (1976), no. 3, 313–332. MR 0417081
    P. J. Stephens, Prime divisors of second order linear recurrences. II, J. Number Theory 8 (1976), no. 3, 333–345. MR 0417082
  • 18. Wen Peng Zhang, On a problem of Brizolis, Pure Appl. Math. (Xi’an) 11 (1995), no. suppl., 1–3 (Chinese, with English and Chinese summaries). MR 1454053

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
Email: holden@rose-hulman.edu

Pieter Moree
Affiliation: Max-Planck-Institut für Mathematik, Vivatsgasse 7, D-53111 Bonn, Germany
Email: moree@mpim-bonn.mpg.de

DOI: http://dx.doi.org/10.1090/S0025-5718-05-01768-0
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.