I'm studing Shor's algorithm, and I have a question regarding the following step:

$$a^r -1 = (a^{r/2}+1)(a^{r/2}-1)=0 \pmod n$$

What would be the result if ${r/2}$ was -1? This will mean it's going to be like this: $(1/a+1)(1/a-1)$.

Will it also be $= 0 \pmod n$?

  • $\begingroup$ Sure, but $r$ is positive and $r/2=-1$ lends to $r=-2$. Aren't you confused with $a^{r/2} \equiv -1 (\mod n)$? $\endgroup$
    – daniel
    May 4, 2014 at 15:25
  • $\begingroup$ @daniel i think i am, but how is r/2 =-1 leading to r=-2? $\endgroup$
    – Scarl
    May 5, 2014 at 15:22
  • $\begingroup$ @daniel however, if r wasn't even then we should return to the first step of the classical part right? as in choose a different a where a<N (N= the number we want to factor) $\endgroup$
    – Scarl
    May 6, 2014 at 4:48

1 Answer 1


What would be the result if $r/2$ was -1?

I assume you meant "how does this work if $a^{r/2} \equiv -1$?

Yes, that does not give us a factorization; however there's an easy fix - use a different value of $a$.

I don't mean "go back to the Quantum Computer and rerun Shor's algorithm with a different base"; instead, select a different value $a'$ and check if $a'^{r} \equiv 1$. It turns out (if the original value of $a$ was randomly selected) that a random selection of $a'$ has a good probability of making this work; once that works, you can then look at $a'^{r/2} \pm 1$; those have a good probability of yielding a factorization.

The other possible complication is "what if the $r$ value that Shor's algorithm hands you happens to be odd?"; it turns out a similar approach works; select a random $a'$, and compute $a'^{2^{\lambda}r}$ for $\lambda$ small (0 until, say, $\log_2(n/r)$); if you find a $\lambda$ with $a'^{2^{\lambda}r} \not\equiv 1$ and $a'^{2^{\lambda+1}r} \equiv 1$, that has a good probability of yielding a factorization (and, yes, this looks a lot like how the Miller Rabin primality test works).

In addition, if you can't find a value $a'$ for which $a'^{2^{\lambda}r} \equiv 1$, you can also compute $\gcd(n, a'^{2^{\lambda}r}-1 \bmod n)$; that also yields a factor in some rare cases.

The bottom line is that, given an output of Shor's algorithm, we have good fast probabilistic methods for obtaining the factorization (which fail with low probability if $a$ was selected randomly [1]); the method isn't quite as simple as "plug in $r$ and $n$ into this simple deterministic algorithm, and out pops the factorization."

[1]: The failure case happens if the order of $a$ modulo $p-1$ happens to be significantly smaller than $p-1$ (and the same modulo $q-1$; that final test covers the case that only one of them is significantly smaller).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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