# Optimising shor's algorithm [closed]

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

• If you don't reduce modulo $n$ in each step during your exponentiation by square and multiply, intermediate results will get huge. But save your time implementing it yourself, do simply what poncho suggested. – j.p. Sep 21 '19 at 7:26

I believe that the python built-in pow(g, p/2, n) does what you want fairly quickly...
• That helps because\begin{align}\gcd((g^{p/2}-1),n)&=\gcd(((g^{p/2}-1)\bmod n),n)\\&=\gcd((((g^{p/2})\bmod n)-1)\bmod n),n)\\&=\gcd(((g^{p/2})\bmod n)-1,n)\end{align} – fgrieu Sep 21 '19 at 7:39