Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-25T08:17:55.501Z Has data issue: false hasContentIssue false
  • English
  • Français

COUNTING FIXED POINTS, TWO-CYCLES, AND COLLISIONS OF THE DISCRETE EXPONENTIAL FUNCTION USING p-ADIC METHODS

Part of: Computational number theory Diophantine equations Multiplicative number theory Communication, information

Published online by Cambridge University Press:  22 November 2012

JOSHUA HOLDEN  and
MARGARET M. ROBINSON
JOSHUA HOLDEN
Affiliation:
Department of Mathematics, Rose-Hulman Institute of Technology, Terre Haute, IN 47803, USA (email: [email protected])
MARGARET M. ROBINSON*
Affiliation:
Department of Mathematics and Statistics, Mount Holyoke College, 50 College Street, South Hadley, MA 01075, USA (email: [email protected])
*
✉For correspondence; e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Brizolis asked for which primes p greater than 3 there exists a pair (g,h) such that h is a fixed point of the discrete exponential map with base g, or equivalently h is a fixed point of the discrete logarithm with base g. Various authors have contributed to the understanding of this problem. In this paper, we use p-adic methods, primarily Hensel’s lemma and p-adic interpolation, to count fixed points, two-cycles, collisions, and solutions to related equations modulo powers of a prime p.

Keywords

Brizolisdiscrete logarithmdiscrete exponentialHensel’s lemmap-adic interpolationfixed pointstwo-cyclescollisions

MSC classification

Secondary: 11D88: $p$-adic and power series fields 11N37: Asymptotic results on arithmetic functions 11Y16: Algorithms; complexity 94A60: Cryptography
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 92 , Issue 2 , April 2012 , pp. 163 - 178
Copyright
Copyright © Australian Mathematical Publishing Association Inc. 2012

Footnotes

The first-named author thanks the Hutchcroft Fund at Mount Holyoke College for support.

References

[1]Balog, A., Broughan, K. A. and Shparlinski, I. E., ‘On the number of solutions of exponential congruences’, Acta Arith. 148 (2011), 93–103.Google Scholar
[2]Bourbaki, N., Commutative Algebra: Chapters 1–7, 1st edn (Addison-Wesley, Reading, MA, 1972).Google Scholar
[3]Bourgain, J., Konyagin, S. V. and Shparlinski, I. E., ‘Product sets of rationals, multiplicative translates of subgroups in residue rings, and fixed points of the discrete logarithm’, Int. Math. Res. Not. IMRN rnn090 (2008), 29.Google Scholar
[4]Bourgain, J., Konyagin, S. V. and Shparlinski, I. E., ‘Distribution of elements of cosets of small subgroups and applications’, Int. Math. Res. Not. IMRN rnr097 (2011), 42.Google Scholar
[5]Campbell, M., ‘On fixed points for discrete logarithms’ MA Thesis, University of California at Berkeley, 2003.Google Scholar
[6]Cobeli, C. and Zaharescu, A., ‘An exponential congruence with solutions in primitive roots’, Rev. Roumaine Math. Pures Appl. 44 (1999), 15–22.Google Scholar
[7]Drakakis, K., ‘Three challenges in Costas arrays’, Ars Combin. 89 (2008), 167–182.Google Scholar
[8]Field, R., Gargeya, V., Robinson, M. M., Schoenberg, F. and Scott, R., ‘The Igusa local zeta function for x m+y n’, Technical Report, Mount Holyoke College, 1994, available at http://arxiv.org/abs/1207.2474.Google Scholar
[9]Glebsky, L., ‘Cycles in repeated exponentiation modulo p n’, Preprint, 2010, available athttp://arxiv.org/abs/1006.2500.Google Scholar
[10]Glebsky, L. and Shparlinski, I., ‘Short cycles in repeated exponentiation modulo a prime’, Des. Codes Cryptogr. 56 (2010), 35–42.Google Scholar
[11]Gouvea, F. Q., p-adic Numbers: An Introduction, 2nd edn (Springer, Berlin, 1997).Google Scholar
[12]Guy, R. K., Unsolved Problems in Number Theory, 3rd edn (Springer, New York, 2004).Google Scholar
[13]Holden, J., ‘Addenda/corrigenda: fixed points and two-cycles of the discrete logarithm’, Rose-Hulman Institute of Technology Mathmatical Sciences Technical Report Series 02-12, 2002, available at http://arxiv.org/abs/0208028.Google Scholar
[14]Holden, J., ‘Fixed points and two-cycles of the discrete logarithm’, in: Algorithmic Number Theory (ANTS 2002), Lecture Notes in Computer Science, 2369 (eds. Fieker, C. and Kohel, D. R.) (Springer, Berlin, 2002), pp. 405–415.Google Scholar
[15]Holden, J. and Moree, P., ‘Some heuristics and results for small cycles of the discrete logarithm’, Math. Comp. 75 (2006), 419–449.Google Scholar
[16]Igusa, J., Lectures on Forms of Higher Degree, 1st edn (Springer, Berlin, 1979).Google Scholar
[17]Koblitz, N., p-adic Numbers, p-adic Analysis, and Zeta-Functions, 2nd edn (Springer, New York, 1984).Google Scholar
[18]Levin, M., Pomerance, C. and Soundarajan, K., ‘Fixed points for discrete logarithms’, in: Algorithmic Number Theory (ANTS-IX), Lecture Notes in Computer Science, 6197 (eds. Hanrot, G., Morain, F. and Thomé, E.) (Springer, Berlin, 2010), pp. 6–15.Google Scholar
[19]Menezes, A. J., van Oorschot, P. C. and Vanstone, S. A., Handbook of Applied Cryptography (CRC Press, Boca Raton, FL, 1996).Google Scholar
[20]Somer, L., ‘The residues of n n modulo p’, Fibonacci Quart. 19 (1981), 110–117.Google Scholar
[21]Zhang, W. P., ‘On a problem of Brizolis’, Pure Appl. Math. (Xi’an) 11(suppl.) (1995), 1–3.Google Scholar