8

I've been trying to mess around with Qiskit's implementation of Shor's algorithm, and while trying I've noticed that Shor(33), for example, would not output a solution (even with an absurd number of attempts). Qiskit's implementation would retry by itself, so I went on to find an implementation which would give me more control over what's happening and I found this one (https://oreilly-qc.github.io/?p=12-1).

The thing I'm struggling to understand is why, for a given value of a in the modulo function of which Shor attempts to find the period r, and assuring that a has no common factors with the number we're factoring, the period should be found (given a number of tries) and thus the algorithm should succeed. However, Shor(33), with a = 2, does not output any result - just like what happened with Qiskit's implementation. It outputs the correct result, however, when a=5 (33 = 11 * 3). Is there a mathematical explanation for why this happens?

Thank you in advance, I'm quite new to this whole new concept and am just trying to understand this algorithm properly!

Community
  • 1
Nuno Costa
  • 83
  • 4

2 Answers2

8

If $f(x) = a^x \pmod{N}$ passes through $-1$, that value of $a$ won't work. For example, $a=2$ fails for $N=33$ because $2^5 = 32 \equiv -1 \pmod{33}$. This should have been mentioned in whatever explanation of Shor's algorithm you were following.

Craig Gidney
  • 44,299
  • 1
  • 41
  • 116
5

What you should have seen in texts is the statement that you have to pick $a$ at random from the numbers that are coprime to $N$. There are then certain claims about the order, $r$ that you get:

  • with high probability, $r$ is even
  • with high probability $a^{r/2}$ is not $\pm 1\text{ mod }N$.

If either of those conditions fail, you have to start again with a different $a$.

The second point here is critical to your case, because what you're wanting is that the factors of $N$ are split between the two terms $a^{r/2}\pm 1$, not all lumped into one of them.

So, all that's happened is that your not very random choice of $a=2$ as failed the high-likelihood conditions.

DaftWullie
  • 62,671
  • 4
  • 55
  • 140