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?

  • 1
    $\begingroup$ 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). $\endgroup$ – Ella Rose Feb 15 '18 at 23:12

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.

  • 2
    $\begingroup$ 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$. $\endgroup$ – fgrieu Feb 15 '18 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.