8
$\begingroup$

For an integer, $N$, to be factorised, with $a$ (uniformly) chosen at random between $1$ and $N$, with $r$ the order of $a\mod N$ (that is, the smallest $r$ with $a^r\equiv 1\mod N$):

Why is that in Shor's algorithm we have to discard the scenario in which $a^{r/2} =-1 \mod N$? Also, why shouldn't we discard the scenario when $a^{r/2} = 1 \mod N$?

$\endgroup$

migrated from stackoverflow.com Apr 17 '18 at 8:18

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ This doesn't strictly have to do with quantum computing. We're talking here about the classical algorithm. It's just that Shor's algorithm gives us a good way of finding the order, $r$, but you can do this classically as well. $\endgroup$ – DaftWullie Apr 17 '18 at 9:12
  • 1
    $\begingroup$ @DaftWullie Although that is true, you can only know this by having knowledge of Shor's algorithm (i.e. QC knowledge). The question as stated: "Why can't we do Shor on these inputs?" is about QC. The answer doesn't contain much QC, but to know what answer to give, you must nevertheless know about Shor's algorithm. $\endgroup$ – Discrete lizard Apr 17 '18 at 10:09
2
$\begingroup$

The requirement that $a^r\equiv 1\mod N$ is equivalent to requiring that $a^r - 1\equiv 0\mod N$.

We want a number, $b$, such that the greatest common denominator of $b$ and $N$ is a proper factor of $N$ (i.e. is a factor $\neq 1, N$).

We also have that $a^r-1 = \left(a^{r/2}-1\right)\left(a^{r/2}+1\right)$.

So, we take $b = a^{r/2}-1$. We know that $r$ is the smallest number such that $a^r = 1\mod N$, showing that $a^{r/2}\neq 1\mod N$ and so $\gcd\left(a^{r/2}-1, N\right)\neq N$ (as otherwise, $N$ would divide $b$).

By Bézout's identity, if $\gcd\left(a^{r/2}-1, N\right)=1, \exists\, x_1, x_2\in\mathbb Z \text{ s.t. } \left(a^{r/2}-1\right)x_1+Nx_2 = 1$, or $\left(a^r-1\right)x_1+N\left(a^{r/2}+1\right)x_2 = a^{r/2}+1$. As $N$ divides $a^r-1$, this gives that $N$ divides $a^{r/2}+1$, or $a^{r/2} = -1\mod N$.

This gives that the requirement $a^{r/2}\neq -1\mod N$ (alongside the constraint on $r$) is enough to determine that the greatest common denominator of $a^{r/2} - 1$ and $N$ is a proper factor of $N$.

$\endgroup$
2
$\begingroup$

There is no scenario of $a^{r/2}\equiv 1\text{ mod }N$ because you have already assumed that $r$ is the smallest value such that $a^r\equiv1\text{ mod }N$, and $r/2$ is smaller than $r$.

As you why you have to discount $a^{r/2}\equiv -1\text{ mod }N$, the point is that you've found something that satisfies $(a^r-1)=kN$ for some integer $k$. This factors as $(a^{r/2}-1)(a^{r/2}+1)=kN$ if $r$ is even. Either, one of the terms $(a^{r/2}\pm 1)$ is divisible by $N$, or each contains different factors of $N$. We want them to contain different factors so that we can computer $\text{gcd}(a^{r/2}\pm1,N)$ to find a factor. So, we specifically want that $a^{r/2}\pm 1\neq 0 \text{ mod }N$. One case has been eliminated as stated above by requiring $r$ to be as small as possible. The other we have to explicitly discount.

$\endgroup$
2
$\begingroup$

If $a^{r/2} \equiv -1$, then $a^{r/2}$ is a trivial square root of $1$ instead of an interesting square root. We already knew that $-1$ is a square root of $1$. We need a square root we didn't already know.

Suppose I give you a number $x$ such that $x^2 = 1 \pmod{N}$. You can rewrite this equation as:

$$\begin{align} x^2 &= 1 + k \cdot N \\ x^2 - 1 &= k \cdot N \\ (x+1)(x-1) &= k \cdot N \end{align} $$

The key thing to realize is that this equation is trivial when $x$ is $\pm 1 \bmod N$. If $x\equiv -1$, then the left hand side is $0 \bmod N$ because the factor $(x+1)\equiv 0$. The same thing happens if $x \equiv +1$, but with the other factor.

In order for both $(x+1)$ and $(x-1)$ to be interesting (i.e. non-zero mod $N$), we need $x$ to be an extra square root of $1$. A square root besides the obvious $+1$ and $-1$ answers. When that happens, it is impossible for the prime factors of $N$ to all go into $(x+1)$ or all go into $(x-1)$, and so $\gcd(x+1, N)$ is guaranteed to give you a factor of $N$ instead of a multiple of $N$.

For example, if $N=221$ then $x=103$ is an extra square root of 1. And indeed, both $\gcd(x+1, N) = \gcd(104, 221) = 13$ and $\gcd(x-1, N) = \gcd(102, 221) = 17$ are factors of $221$. Whereas if we had picked the boring square root $x=-1\equiv 220$, then neither $\gcd(x+1,N) = \gcd(221, 221) = 221$ nor $\gcd(x-1,N) = \gcd(219,221) = 1$ are factors of $221$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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