# Finding tetration in a multiplicative group modulo p

I have a variant on the discrete logarithm problem, involving finding tetration in a multiplicative cyclic group of integers modulo a large prime $$p$$:

$$a = x^x \mod p$$

Where $$a$$ and $$p$$ are known, and $$p$$ is not necessarily a safe prime. Can $$x$$ efficiently be found or is this at least as hard as the DLP?

• Like DLP in the multiplicative group of integers modulo n, except that the base must equal the exponent. – Laurence Aug 24 '19 at 20:29
• In DLP we know that base, In this case, there can be more than one pair for a given $a$ or none. – kelalaka Aug 24 '19 at 20:35
• " Can x efficiently be found or is this at least as hard as the DLP?" Probably, it is neither one nor the other, but somewhere in between. For some values $a$, it might have multiple solutions or none - so maybe it is easy to find the solution for some and difficult for others. Since the set of solutions don't have a group structure (or something similar), I can't think of a way to define any security property, which would work for all $a$. – tylo Aug 24 '19 at 22:07
• Also please note that, algebraically speaking, the exponent will not belong to the same group as the base. Furthermore, the group of integers modulo a prime p, will not be cyclic for any primes greater than 3. There will however always be cyclic sub groups of some prime order q, such that q divides (p-1). Consequently the problem has to be redefined to make better sense. – Henrick Hellström Aug 25 '19 at 14:04
• Usually tetration, sometimes written ${^nx}$, means $\underbrace{x^{x^{{\cdot^{\cdot^{\cdot^x}}}}}}_{\text{$n$times}}$ rather than just $x^x$. The function $x \mapsto x^x$ is sometimes called the ‘self-power map’. But it's not defined on $\mathbb Z/p\mathbb Z$ without a choice of map to $\mathbb Z/\phi(p)\mathbb Z$. For example, if $p = 11$, for $x = 19$, do you take it to be $(19 \bmod p)^{(19 \bmod p) \bmod \phi(p)} \bmod p = 8^8 \bmod 11 = 5$, or do you take it to be $(19 \bmod p)^{19 \bmod \phi(p)} \bmod p = 8^9 \bmod 11 = 7$? – Squeamish Ossifrage Aug 26 '19 at 15:07

Given any prime $$p$$ and integer $$a$$, the following procedure finds an integer $$x\in\mathbb Z_{\geq0}$$ such that $$x^x\equiv a\pmod p \,\text.$$
1. Pick some positive integer $$e$$ coprime to $$p-1$$. (For example, $$e=1$$ always works.)
2. Write the prospective solution as $$x=e+k(p{-}1)$$ with $$k\in\mathbb Z_{\geq0}$$.
3. Since the order of $$x$$ must be a divisor of $$p-1$$, the equation becomes $$(e+k(p{-}1))^{e}\bmod p=a \,\text.$$ Raise everything to the power of $$f:=e^{-1}\bmod(p{-}1)$$ to obtain $$e+k(p{-}1) \equiv a^f \pmod p \,\text.$$
4. Simply solve this congruence for $$k$$, that is, compute $$k := (e-a^f)\bmod p \,\text.$$
5. Output $$x:=e+k(p{-}1)$$.
Note that the expected size of $$x$$ is approximately $$p^2$$.