Tìm $i$ trong phép bổ túc khó đến mức nào $^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \ mod P$ cho $v\in[1,P-1]$

Để cho $g\in\mathbb N$ sẽ có nhiều nhất $O(\log P)$ chuẩn độ riêng biệt modulo $P$. Vì vậy, chỉ có một số ít ví dụ mà $|\{{}^jg\mod P\}|=P-1$. Trong các trường hợp khác, nếu modun tetraration $P$ có thể được tính toán một cách hiệu quả, thì vấn đề dễ dàng được giải quyết bằng cách làm cạn kiệt.

Để hiểu kích thước nhỏ của $|\{{}^jg\mod P\}|$, lưu ý rằng nếu $P$ không phân chia $g$ Sau đó $i\ge 1$ theo định lý Euler $${}^ig\equiv g^{{}^{i-1}g}\equiv g^{{}^{i-1}g\mod{\phi(P)}}\pmod P.$ $ Bây giờ chúng tôi lưu ý rằng ${}^{i-1}g\mod{\phi(P)}$ đảm nhận tối đa $\phi(\phi(P))$ các giá trị khác nhau và các chu kỳ này với thời gian tối đa $\phi(\phi(P))$. Nó theo đó cho $i\ge 1$, ${}^ig\mod P$ chiếm nhiều nhất $\phi(\phi(P))$ các giá trị. Lặp lại đối số viết $\phi_k(x)$ cho $k$chức năng totient lặp đi lặp lại $\phi_1(x)=\phi(x)$, $\phi_k(x)=\phi(\phi_{k-1}(x))$. Sau đó chúng tôi thấy rằng cho $i\ge k$, ${}^{i-k}g\mod{\phi_k(P)}$ đảm nhận tối đa $\phi_{k+1}(P)$ các giá trị khác nhau và do đó cho $i\ge k$, ${}^ig\mod P$ chiếm nhiều nhất $\phi_{k+1}(P)$ các giá trị. Có một số bỏ qua ở đây về chi tiết khi $g$ có một yếu tố chung với $\phi_k(P)$.

Bây giờ, chúng tôi lưu ý rằng đối với tất cả $n>2$ chúng ta có $2|\phi(n)$ và điều đó cho tất cả $m$ chúng ta có $\phi(2m)\le m/2$. Nó sau đó $\phi_k(P)\le P/2^{k-1}$. Cũng bởi vì $\phi_k(P)$ là một số nguyên, cho $k>\lceil\log_2P\rceil+1$ chúng ta có $\phi_k(P)=1$. Vì vậy, nếu chúng ta viết $L=\lceil\log_2P\rceil+1$ chúng tôi có cho $i,j>L$ ${}^ig\equiv{}^jg\pmod P$.

Việc tính toán các phép tứ phân có thể được thực hiện bằng các phương pháp bình phương và nhân với điều kiện là người ta có thể tính toán tất cả các $\phi_k(P)$.