1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Like DLP in the multiplicative group of integers modulo n, except that the base must equal the exponent. $\endgroup$ – Laurence Aug 24 '19 at 20:29
  • $\begingroup$ In DLP we know that base, In this case, there can be more than one pair for a given $a$ or none. $\endgroup$ – kelalaka Aug 24 '19 at 20:35
  • 2
    $\begingroup$ " 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$. $\endgroup$ – tylo Aug 24 '19 at 22:07
  • $\begingroup$ 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. $\endgroup$ – Henrick Hellström Aug 25 '19 at 14:04
  • 1
    $\begingroup$ 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$? $\endgroup$ – Squeamish Ossifrage Aug 26 '19 at 15:07
3
$\begingroup$

As pointed out in the comments, it's not quite clear what the problem is, but here's an easy algorithm for the (arguably) most natural interpretation.

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$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.