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.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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...

  • 1
    $\begingroup$ 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}$$ $\endgroup$ – fgrieu Sep 21 at 7:39
  • $\begingroup$ Thanks for you both, and @fgrieu explanation is what i was looking for $\endgroup$ – Jamil Hneini Sep 21 at 10:01

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