EDIT: Am greșit ceva (vezi comentariile la răspuns). Această întrebare conține câteva afirmații false EditEnd.
Pentru tetrarea modulo prim $P$
$$^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \mod P$$
cu potrivit $g,P$ astfel încât
$$|\{^jg \mod P\}| = P-1 \text{ }\text{ , sau }\text{ } v\in[1,P-1] $$
Dat $P,g,v$, cât de greu este găsirea aferentă $i$?
Mai greu decât DLP? (găsirea $i$ pentru $g^i \equiv v \mod P$)
Sunt interesat de numărul de pași ($O$ notație).
Pentru a o compara cu problema normală DLP presupunem un pas - deci $g^c$ și $g\cdot c$ cu constantă $c$ are nevoie de același timp.
Pentru a obține toate valorile $v$ variabilele $g,P$ nevoie de o proprietate specială:
$$^{P-1}g \equiv 1 \mod P$$
$$\forall j \in [1,N-2]: \text{ }^{j}g \not\equiv 1 \mod P$$
De asemenea, presupunem $g,P$ sunt alese cât mai sigur posibil (cum ar fi $P = 2q+1$, cu $q$ prim (de asemenea, mai bine aici?))
exemplu de jucărie:
Cu $P=5, g=3$ succesiunea ar fi
$$\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{divizat}$$
Sau $P=23, g=20$ sau $P=59, g=39$
întrebarea principală:
- Câți pași sunt necesari pentru a calcula $i$ din dat $v,g,P$?
intrebari secundare:
Câți pași sunt necesari pentru a calcula rezultatul $v$ pentru dat $i,g,P$? Mai rapid decât $O(i)$?
Dacă o valoare $v_i$ pentru un anume $i$ este cunoscută următoarea valoare $v_{i+1}$ poate fi calculat cu $$ ^{i+1}g \equiv g^{v_{i}} \equiv v_{i+1} \mod P$$
Este, de asemenea, posibil să se calculeze $v_{i-1}$ din $v_{i}$ ? Sau este similar cu DLP-ul?
