|
Some heuristics and results for small cycles of the discrete logarithm
Author(s):
Joshua
Holden;
Pieter
Moree.
Journal:
Math. Comp.
75
(2006),
419-449.
MSC (2000):
Primary 11A07;
Secondary 11N37, 94A60, 11-04
Posted:
June 28, 2005
Retrieve article in:
PDF DVI PostScript
Abstract |
References |
Similar articles |
Additional information
Abstract:
Brizolis asked the question: does every prime  have a pair  such that  is a fixed point for the discrete logarithm with base  ? 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  and  . 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:
-
- 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 http://xxx.lanl.gov/abs/math.NT/0208028
- 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
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:
10.1090/S0025-5718-05-01768-0
PII:
S 0025-5718(05)01768-0
Received by editor(s):
January 4, 2004
Received by editor(s) in revised form:
August 30, 2004
Posted:
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)
Copyright of article:
Copyright
2005,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
Comments: webmaster@ams.org