# How to compute this equation $(g^k)^\alpha\bmod p$

I have a question about implementation. How is an operation like this implemented?

$$(g^k)^\alpha\bmod p$$

With all $g$, $k$, and $\alpha$ being large numbers. The thing that I find tricky is that the $k$ is large and in that operation I can't use the modular exponentiation apparently. Once this number is calculated, I can imagine the modular exponentiation with $\alpha$ and $p$ being feasible, but $$g^k$$ can easily explode. What's the right way to implement something like this?

• You may be interested in exponentiation by squaring if you were just using the naive method for exponentiating before (it is not clear what/where your issue is from your question). – Ella Rose Feb 15 '18 at 23:12

## 1 Answer

in that operation I can't use the modular exponentiation apparently

Why not? After all,

$$(g^k)^\alpha \bmod p = (g^k \bmod p)^\alpha \bmod p$$

That is, you can compute $g^k$ modulo $p$, and use that as the intermediate result.

• Further, if $p$ is prime, using Fermat's little theorem, $(g^k)^\alpha \bmod p\ =\ g^{k\,\alpha\bmod(p-1)}\bmod p$. That will pay if $k\,\alpha\gg p$. – fgrieu Feb 15 '18 at 22:33