2
$\begingroup$

EDIT: I messed up something (see comments at answer). This question contains some false statements EditEnd.

For tetration modulo prime $P$ $$^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \mod P$$ with suitable $g,P$ so that $$|\{^jg \mod P\}| = P-1 \text{ }\text{ , or }\text{ } v\in[1,P-1] $$

Given $P,g,v$, how difficult is finding the related $i$?
Harder than DLP? (finding $i$ for $g^i \equiv v \mod P$)
I'm interested at the number of steps ($O$ notation ).
To compare it with the normal DLP problem we assume one step - so $g^c$ and $g\cdot c$ with constant $c$ does need the same time.


To get all values $v$ the variables $g,P$ need some special property: $$^{P-1}g \equiv 1 \mod P$$ $$\forall j \in [1,N-2]: \text{ }^{j}g \not\equiv 1 \mod P$$ We also assume $g,P$ are picked as safe as possible (like $P = 2q+1$, with $q$ prime (also better here?))


toy example:

With $P=5, g=3$ the sequence would be $$\begin{split} &[3, 3^3, 3^{3^3}, 3^{3^{3^3}}] \mod 5 \\ \equiv&[3, 3^3\equiv 2, 3^{2} \equiv 4, 3^{4} \equiv 1] \mod 5 \\ \equiv&[3, 2, 4, 1] \mod 5 \end{split}$$

Or $P=23, g=20$ or $P=59, g=39$


main-question:

  • How many steps needed to compute $i$ out of given $v,g,P$?

side-questions:

  • How many steps needed to compute the result $v$ for given $i,g,P$? Faster than $O(i)$?

  • If a value $v_i$ for a certain $i$ is known the next value $v_{i+1}$ can be computed with $$ ^{i+1}g \equiv g^{v_{i}} \equiv v_{i+1} \mod P$$ Is it also possible to compute $v_{i-1}$ out of $v_{i}$ ? Or is it similar to the DLP?

$\endgroup$
2
  • $\begingroup$ Is there even an efficient way to compute it in the forward direction, meaning compute the map $i \mapsto {}^ig$? This is not clear to me, and is a desirable part of (standard) exponentiation. $\endgroup$
    – Mark
    Feb 25, 2022 at 4:16
  • $\begingroup$ @Mark I don't know either. I meant this with the first 'side-question' if i understood you correctly. However I'm looking for something which is locally ($i \pm 1 $) easy to compute but hard for a certain index $i$. It could serve as random permutation. If $i \mapsto ^ig$ is easy to compute ($O(1)$) it would only take $O(\sqrt{P})$ steps to find $i$ for given $v$ (like for DLP) or even less. I would like a $P$ as small as possible with same security. $\endgroup$
    – J. Doe
    Feb 25, 2022 at 5:59

1 Answer 1

2
$\begingroup$

For a given $g\in\mathbb N$ there will be at most $O(\log P)$ distinct titrations modulo $P$. Thus there are only a small number of examples where $|\{{}^jg\mod P\}|=P-1$. In other cases, if the tetration modulo $P$ can be effectively computed, then the problem is easy to solve by exhaustion.

To understand the small size of $|\{{}^jg\mod P\}|$, note that for if $P$ does not divide $g$ then for $i\ge 1$ by Euler's theorem $${}^ig\equiv g^{{}^{i-1}g}\equiv g^{{}^{i-1}g\mod{\phi(P)}}\pmod P.$$ We now note that ${}^{i-1}g\mod{\phi(P)}$ takes on at most $\phi(\phi(P))$ different values and the these cycle with period at most $\phi(\phi(P))$. It follows that for $i\ge 1$, ${}^ig\mod P$ takes on a most $\phi(\phi(P))$ values. Iterating the argument write $\phi_k(x)$ for the $k$-iterated totient function $\phi_1(x)=\phi(x)$, $\phi_k(x)=\phi(\phi_{k-1}(x))$. We then see that for $i\ge k$, ${}^{i-k}g\mod{\phi_k(P)}$ takes on at most $\phi_{k+1}(P)$ different values and hence for $i\ge k$, ${}^ig\mod P$ takes on a most $\phi_{k+1}(P)$ values. Theres some elision of here about details when $g$ has a factor in common with $\phi_k(P)$.

Now, we note that for all $n>2$ we have $2|\phi(n)$ and that for all $m$ we have $\phi(2m)\le m/2$. It follows that $\phi_k(P)\le P/2^{k-1}$. Also because $\phi_k(P)$ is an integer, for $k>\lceil\log_2P\rceil+1$ we have $\phi_k(P)=1$. Thus if we write $L=\lceil\log_2P\rceil+1$ we have for $i,j>L$ ${}^ig\equiv{}^jg\pmod P$.

Computing the tetrations can be done by square-and-multiply methods provided that one can compute all of the $\phi_k(P)$.

$\endgroup$
5
  • $\begingroup$ Sorry I forgot some mod operator (changed it): I meant $|\{^jg \mod P\}| = P-1 $. So $g$ and $P$ are picked in that way that we get $P-1$ different values ($\in \{1,..,P-1\}$) for $j \in [1,P-1]$ $\endgroup$
    – J. Doe
    Feb 25, 2022 at 6:11
  • $\begingroup$ I understand this and by the argument above this restricts $P$ to be 2, 3 or 5. $\endgroup$
    – Daniel S
    Feb 25, 2022 at 6:17
  • $\begingroup$ Why $P$ can only be $2,3,5$? E.g. the values $P=23$ with $g=20$ do work fine. They can produce all values from $1$ to $22$. The related values would be: $[20,18,2,9,5,10,8,6,16,13,14,4,12,3,19,17,7,21,15,11,22,1]$ \ \ Also why is it $g^{^{i-1}g \mod \phi(P)}$ and not $g^{^{i-1}g \mod P}$? $\endgroup$
    – J. Doe
    Feb 25, 2022 at 6:55
  • 1
    $\begingroup$ Ah I see. You're not computing ${}^ig\mod P$, but the $i$th iteration of the map $x\mapsto g^x\mod P$ with starting value $g$. These are not the same thing (e.g. $3^{3^3}=3^{27}\equiv 2\pmod 5$). $\endgroup$
    – Daniel S
    Feb 25, 2022 at 7:08
  • $\begingroup$ Oh, thank you for that hint! I thought they are equal. It worked out for the tested example. So I'm actually looking for an answer of that $i$th iteration. $\endgroup$
    – J. Doe
    Feb 25, 2022 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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