Finding such a square root is the key to the decomposition of a number $N$. To understand this, suppose we have found a value $x$ such that $$x^2 \equiv 1 \pmod N.$$ Moving the 1 to the other side we obtain that $$x^2-1 \equiv 0 \pmod N,$$ which can be factored as $$(x-1)(x+1) \equiv 0 \pmod N.$$ Suppose that $N$ can be factored as the product of two primes $p$ and $q$ which we would like to find. From the above equation we can deduce that the product of $(x-1)$ and $(x+1)$ is a multiple of $N$, so there will exist an integer $k$ such that the following equality is satisfied: $$(x-1)(x+1) = kN = kpq.$$ So, recapitulating, we will find a nontrivial square root $x$ of $N$, which gives us the number $(x-1)$ and the number $(x+1)$, and we would like to recover $p$ and $q$. Now, if we decompose $(x-1)$ and $(x+1)$ into prime factors, then $p$ and $q$ must appear in the decomposition (because $(x-1)(x+1) = kpq$). However, there is a more important statement that we will prove in the next exercise. --- ***Exercise S.2.2***. Let $N$ be an integer that is a product of two primes $p$ and $q$. Prove that if $x$ is a nontrivial square root of $N$ such that $(x-1)(x+1) = kN$ for some integer $k$, then $(x-1)$ is a multiple of one of the primes and $(x+1)$ is a multiple of the other.

Solution.

If $x$ is nontrivial square root modulo $N$ it belongs to the set $\{2,3,...,N-2\}$, so $(x-1) < N$ and $(x+1) < N$. In this situation $p$ and $q$ are factors such that one belongs to the decomposition of $(x-1)$ and the other to that of $(x+1)$. To see this, suppose for example that $(x+1)$ had $p$ and $q$ as factors, then $(x+1) = pqs$ for a certain integer $s$. The key is that this is not possible since $N = pq$ and therefore $(x+1) = Ns \ge N$, which contradicts what we know about $x$. ▢

--- In addition to nontrivial square roots, to factor numbers classically, we will also need to remember the concept of **greatest common divisor** (GCD). We can see it as an algorithm that takes two integers as input and returns the largest possible product using the common prime factors. As an example, $$\text{GCD}(150, 250) = 50.$$ This is because $150 = 5 \cdot 5 \cdot 3\cdot 2$ and $250 = 5 \cdot 5 \cdot 5 \cdot 5 \cdot 2$. The common factors are $5$,$5$ and $2$, which we can multiply together to obtain $50$. In addition, this algorithm can be efficiently implemented in a classical way through what is known as [**Euclid's algorithm**](https://en.wikipedia.org/wiki/Euclidean_algorithm). We know $N = pq$ and $(x+1) = sp$, with $s$ being an integer whose decomposition will not depend on $q$. Knowing this, calculating the greatest common divisor we will get that: $$p = \text{GCD}((x-1), N),$$ and similarly, $$q = \text{GCD}((x+1), N).$$ --- ***Exercise S.2.3***. Knowing that $2^4 \equiv 1 \pmod {15}$, decompose 15 into its prime factors using the strategy described above.

Solution.

Since $2^4 \equiv 1 \pmod {15}$, we know that $(2^2)^2 \equiv 1 \pmod {15}$, so $4$ is a nontrivial square root. If we now calculate the GCD we get that $$p = \text{GCD}(4-1, 15) = 3,$$ $$q = \text{GCD}(4+1, 15) = 5.$$ So the two prime factors of $15$ are $3$ and $5$. ▢

--- With this, we have learned the basics necessary to understand how Shor's algorithm works. We are ready to move on to the quantum part!

Codercise S.2.1 - Nontrivial square roots

Codercise S.2.2 - Prime factors

Nontrivial square roots

Finding prime factors