Optimising shor's algorithm So I've run into this challenge where I was given the guess $g$, and the power $p$ of Shor's algorithm.

All I have to do now is $g^{p/2} - 1$ and then GCD the result with n. But the problem is computing $g^{p/2}$ takes a RIDICULOUS amount of time, even with the exponentiation by squaring method.

Is there any possibility to optimize this process? Or at least is there a better way to compute $g^{p/2}$?

Note: g and p are both of the order of 40 digits or so, and I was doing the exponentiation by squaring using python 3.7
I believe that the python built-in pow(g, p/2, n) does what you want fairly quickly...