Насколько сложно найти $i$ в тетрации $^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \ мод P$ для $v\in[1,P-1]$

Для данного $г\в\mathbb N$ будет максимум $ О (\ журнал P) $ различные титрования по модулю $P$. Таким образом, имеется лишь небольшое количество примеров, когда $|\{{}^jg\mod P\}|=P-1$. В других случаях, если тетрация по модулю $P$ может быть эффективно вычислено, то задача легко решается перебором.

Чтобы понять малый размер $|\{{}^jg\mod P\}|$, обратите внимание, что если $P$ не разделяет $г$ тогда для $i\ge 1$ по теореме Эйлера $${}^ig\equiv g^{{}^{i-1}g}\equivg^{{}^{i-1}g\mod{\phi(P)}}\pmod P.$ $ Теперь отметим, что ${}^{i-1}g\mod{\phi(P)}$ принимает не более $\фи(\фи(P))$ различные значения и эти циклы с периодом не более $\фи(\фи(P))$. Отсюда следует, что для $i\ge 1$, ${}^ig\mod P$ берет на себя большую часть $\фи(\фи(P))$ ценности. Итерация аргумента write $\фи_к(х)$ для $к$-итерируемая тотиентная функция $\фи_1(х)=\фи(х)$, $\phi_k(x)=\phi(\phi_{k-1}(x))$. Затем мы видим, что для $i\gek$, ${}^{ik}g\mod{\phi_k(P)}$ принимает не более $\фи_{к+1}(Р)$ различные значения и, следовательно, для $i\gek$, ${}^ig\mod P$ берет на себя большую часть $\фи_{к+1}(Р)$ ценности. Здесь есть некоторые упущения о деталях, когда $г$ имеет общий фактор с $\фи_к(П)$.

Теперь заметим, что для всех $n>2$ у нас есть $2|\фи(п)$ и это для всех $м$ у нас есть $\фи(2м)\ле м/2$. Следует, что $\phi_k(P)\le P/2^{k-1}$. Также из-за $\фи_к(П)$ является целым числом, для $k>\lceil\log_2P\rceil+1$ у нас есть $\фи_к(П)=1$. Таким образом, если мы напишем $L=\lceil\log_2P\rceil+1$ у нас есть для $i,j>L$ ${}^ig\equiv{}^jg\pmod P$.

Вычисление тетраций может быть выполнено методом квадрата и умножения при условии, что можно вычислить все $\фи_к(П)$.