The complexity of modular addition is known: $g + p \mod n$ (for $|p| \approx |g| \approx |n|$) can be computed in $O(n)$.

The complexity of modular multiplication is open though some results are known: by Toom-Cook $g * p \mod n$ can be performed in $O(n^{1.465})$ and by Schönhage–Strassen in $O(n \log n \log \log n)$.

Modular exponentiation can be performed in $O(M(n) k)$ where $M(n)$ is the complexity of multiplication and $k$ is the length in bits of the exponent by the square-and-multiply algorithm.

I am looking for results about the modular arithmetic in general. Are there better complexity results for performing modular exponentiation (over the 'naive' square-and-multiply)? What results are known for modular exponentiation of power towers of height h?

(For $h = 3$: $g^{g^{g}} \mod n$ and for general $h$: $g^{g^{g^{g^{...^g}}}} \mod n$)

The complexity of modular addition is known: $g + p \mod N$ (for $|p| \approx |g| \approx |N|$) can be computed in $O(n = |N|)$.

The complexity of modular multiplication is open though some results are known: by Toom-Cook $g * p \mod N$ can be performed in $O(n^{1.465})$ and by Schönhage–Strassen in $O(n \log n \log \log n)$.

Modular exponentiation can be performed in $O(M(n) k)$ where $M(n)$ is the complexity of multiplication and $k$ is the length in bits of the exponent by the square-and-multiply algorithm.

I am looking for results about the modular arithmetic in general. Are there better complexity results for performing modular exponentiation (over the 'naive' square-and-multiply)? What results are known for modular exponentiation of power towers of height h?

(For $h = 3$: $g^{g^{g}} \mod N$ and for general $h$: $g^{g^{g^{g^{...^g}}}} \mod N$)

The complexity of modular addition is known: $g + p \mod n$ (for $|p| \approx |g| \approx |n|$) can be computed in $O(n)$.

The complexity of modular multiplication is open though some results are known: by Toom-Cook $g * p \mod n$ can be performed in $O(n^{1.465})$ and by Schönhage–Strassen in $O(n \log n \log \log n)$.

Modular exponentiation can be performed in $O(M(n) k)$ where $M(n)$ is the complexity of multiplication and $k$ is the length in bits of the exponent by the square-and-multiply algorithm.

I am looking for results about the modular arithmetic in general. Are there better complexity results for performing modular exponentiation (over the 'naive' square-and-multiply)? What results are known for modular exponentiation of power towers of height h $g^{g^{g^{g^{...^g}}}} \mod n$?

The complexity of modular addition is known: $g + p \mod n$ (for $|p| \approx |g| \approx |n|$) can be computed in $O(n)$.

The complexity of modular multiplication is open though some results are known: by Toom-Cook $g * p \mod n$ can be performed in $O(n^{1.465})$ and by Schönhage–Strassen in $O(n \log n \log \log n)$.

Modular exponentiation can be performed in $O(M(n) k)$ where $M(n)$ is the complexity of multiplication and $k$ is the length in bits of the exponent by the square-and-multiply algorithm.

I am looking for results about the modular arithmetic in general. Are there better complexity results for performing modular exponentiation (over the 'naive' square-and-multiply)? What results are known for modular exponentiation of power towers of height h?

(For $h = 3$: $g^{g^{g}} \mod n$ and for general $h$: $g^{g^{g^{g^{...^g}}}} \mod n$)