Some heuristics and results for small cycles of the discrete logarithm

Holden, Joshua; Moree, Pieter

doi:10.1090/S0025-5718-05-01768-0

Some heuristics and results for small cycles of the discrete logarithm
HTML articles powered by AMS MathViewer

by Joshua Holden and Pieter Moree;

Math. Comp. 75 (2006), 419-449

DOI: https://doi.org/10.1090/S0025-5718-05-01768-0

Published electronically: June 28, 2005

PDF | Request permission

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

Campbell, Mariana, On fixed points for discrete logarithms, Master’s Thesis, 2003.
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
Carl-Gustav Esseen, A stochastic model for primitive roots, Rev. Roumaine Math. Pures Appl. 38 (1993), no. 6, 481–501. MR 1258051
É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, DOI 10.1007/BF01388980
Richard K. Guy, Unsolved problems in number theory, Problem Books in Mathematics, Springer-Verlag, New York-Berlin, 1981. Unsolved Problems in Intuitive Mathematics, 1. MR 656313
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, DOI 10.1007/3-540-45455-1_{3}2
—, Addenda/corrigenda: Fixed points and two-cycles of the discrete logarithm, 2002, unpublished http://xxx.lanl.gov/abs/math.NT/0208028
Mark Kac, Statistical independence in probability, analysis and number theory, The Carus Mathematical Monographs, No. 12, Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York, 1959. MR 110114
Pieter Moree and Peter Stevenhagen, A two-variable Artin conjecture, J. Number Theory 85 (2000), no. 2, 291–304. MR 1802718, DOI 10.1006/jnth.2000.2547
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, DOI 10.5802/jtnb.318
Pieter Moree, Approximation of singular series and automata, Manuscripta Math. 101 (2000), no. 3, 385–399. With an appendix by Gerhard Niklasch. MR 1751040, DOI 10.1007/s002290050222
Pieter Moree, Asymptotically exact heuristics for (near) primitive roots, J. Number Theory 83 (2000), no. 1, 155–181. MR 1767657, DOI 10.1006/jnth.1999.2502
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
Carl Pomerance, Personal communication.
Karl Prachar, Primzahlverteilung, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957 (German). MR 87685
P. J. Stephens, An average result for Artin’s conjecture, Mathematika 16 (1969), 178–188. MR 498449, DOI 10.1112/S0025579300008159
P. J. Stephens, Prime divisors of second-order linear recurrences. I, J. Number Theory 8 (1976), no. 3, 313–332. MR 417081, DOI 10.1016/0022-314X(76)90010-X
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