0
$\begingroup$

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

$\endgroup$
  • 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 '19 at 7:26
2
$\begingroup$

I believe that the python built-in pow(g, p/2, n) does what you want fairly quickly...

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

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