Counting fixed points and rooted closed walks of the singular map $x\mapsto x^{x^n}$ modulo powers of a prime

Abstract

The "self-power" map $x\mapsto x^x$ modulo $m$ and its generalized form $x\mapsto x^{x^n}$ modulo $m$ are of considerable interest for both theoretical reasons and for potential applications to cryptography. In this paper, we use $p$-adic methods, primarily $p$-adic interpolation, Hensel's lemma, and lifting singular points modulo $p$, to count fixed points and rooted closed walks of equations related to these maps when $m$ is a prime power. In particular, we introduce a new technique for lifting singular solutions of several congruences in several unknowns using the left kernel of the Jacobian matrix.

18 pages. Version 2 shortens proofs, reduces redundancy, and introduces new technique for counting rooted closed walks. Version 3 updates title to agree with journal publication

References in corpus (4)

• Congruences involving product of intervals and sets with small multiplicative doubling modulo a prime and applications
• Addenda/Corrigenda: Fixed Points and Two-cycles of the Discrete Logarithm
• Counting Fixed Points, Two-Cycles, and Collisions of the Discrete Exponential Function using p-adic Methods
• Statistics for fixed points of the self-power map