# Confusion about random sampling of integers in Shor's algorithm

My understanding of Shor's algorithm is that you have to carry out the following steps if you are trying to factor $N$:

1. Chose a random number less than $N$. Let's call it $a$.

2. Calculate the period of $a^x \ \text{mod} \ N$. Let's call the period $r$.

3. One of the factors is the GCD of $a^{r/2}+1$ and $N$. The other is the GCD of $a^{r/2}-1$ and $N$.

However this does not work in some cases such as if $N=35$ and $a=10$. You should be getting $5$ and $7$ as the prime factors of $35$, but this is not the case. The period of $10^x \ \text{mod} \ 35$ is $6$. The GCD of $10^{6/2}+1$, $1001$ and $35$ is $7$, which is one of the factors. But the GCD of $10^{6/2}-1$, $999$ and $35$ is $1$, which is not what you should be getting. Why doesn't Shor's algorithm work in this case?

• Notice that Shor's algorithm doesn't need to "always work" in the sense you're asking about. Indeed, suppose you have any probabilistic algorithm which given a number n, outputs either 1 or a nontrivial factor, and if n is not prime it does the latter with probability at least $1/2$. Then we can use this to fully factorize $n$: run it until you get a factor $k$, and then recursively factor $k$ and $n/k$. – Jalex Stark May 5 '18 at 19:35
• Hi! Welcome to Quantum Computing Stack Exchange. Please use MathJax to format mathematical expressions and equations from the next time onwards. I have formatted your question this time. You will find a short MathJax tutorial here. – Sanchayan Dutta May 5 '18 at 19:59

You skipped a step in the algorithm.

1. First check if $N$ is even. $35$ is not even.

2. Next determine if $N=a^b$ for $a \geq 1$ and $b \geq 2$. It's not.

3. Randomly choose $x$ in the range $1$ to $N-1$. If $\text{gcd}(x,N) > 1$ then return the factor $\text{gcd}(x,N)$. This is what you missed. $\text{gcd}(10,35) = 5$ There's no reason to perform order finding if you choose $x = 10$. $x$ should be co-prime to $N$ in order to continue.

For completeness:

1. Find the order $r$ of $x\bmod N$.

2. If $r$ is even and $x^{r/2} \neq -1 \pmod N$ then compute the $\text{gcd}(x^{r/2} -1,N)$ to see if one of these is a non-trivial factor. Otherwise, the algorithm fails.

The reason the algorithm could fail is because you don't have enough qubits to perform the order-finding part to enough precision.

These steps came from Section 5.3.2 of Nielsen & Chuang.

• \mod seems to produce too much spacing. I tried to fix it using \text{mod}. If anyone has a better fix for the spacing and formatting feel free to edit. For reference: tex.stackexchange.com/questions/137073/… – Sanchayan Dutta May 5 '18 at 20:12
• Yeah that’s right. I usually use {\rm } – Andrew O May 5 '18 at 21:14
• I used \bmod (no brackets) and \pmod (with brackets). Looks reasonable to me, but feel free to roll back cc @Blue – Mithrandir24601 May 5 '18 at 22:40
• @Blue Use mkern before pmod --- Origonal: \$x^{r/2}\ne-1\pmod{\text{N}}\$ - Suggested: \$x^{r/2}\ne-1\mkern-12mu\pmod{\text{N}}\$ --- Result: $$x^{r/2}\ne-1\pmod{\text{N}}$$ $$x^{r/2}\ne-1\mkern-12mu\pmod{\text{N}}$$ – Rob May 9 '18 at 6:17
• @cssstyler In this case, you've found two factors of N (9 and 5, one of which is prime) - lets be more general and call these $M_1$ and $M_2$ and you've reduced your problem of factorising N to either being solved (if you just want any factors of N) or you've divided it into one of factoring $M_1$ and $M_2$ i.e. split it into two of the same but smaller problems (in this specific case of 9 and 5, it's even easier as 5 is a prime factor and 9 is $3^2$, so you've solved the problem without a single call to the QC) – Mithrandir24601 May 5 at 20:12