# 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

## closed as off-topic by kelalaka, AleksanderRas, Squeamish Ossifrage, Ella Rose♦Sep 21 at 15:43

This question appears to be off-topic. The users who voted to close gave these specific reasons:

• "Programming questions are off-topic even if you are writing or debugging cryptographic code. Unless your question is specifically about how the cryptographic algorithm, protocol or side-channel (mitigation) works, you should look into asking on Stack Overflow instead." – Squeamish Ossifrage, Ella Rose
• "Questions asking for solutions to crypto puzzles or homework exercises are off-topic. While we do accept questions about homework problems, such questions must contain more than just a verbatim copy of the assignment, and should preferably ask for general solving techniques rather than just a solution to a specific puzzle or exercise." – kelalaka, AleksanderRas
If this question can be reworded to fit the rules in the help center, please edit the question.

• 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 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 at 7:39