9

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$?

Mithrandir24601
  • 3,796
  • 3
  • 24
  • 45
Tech Solver
  • 613
  • 4
  • 10

3 Answers3

4

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.

DaftWullie
  • 62,671
  • 4
  • 55
  • 140
3

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$.

Sanchayan Dutta
  • 17,945
  • 8
  • 50
  • 112
Craig Gidney
  • 44,299
  • 1
  • 41
  • 116
2

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$.

Mithrandir24601
  • 3,796
  • 3
  • 24
  • 45