In this section we will show how quantum computers can break RSA encryption by factorising numbers into primes efficiently

✨ Proposition: let $p$ and $q$ be integers and $r$ the remainder of division of $p$ by $q$. Assuming that $r\ne 0$ we have $\gcd(p,q)=\gcd (q,r)$

🧚‍♂️ Proof: we show that each side divides the other side

Euclid’s algorithm

  1. Initialization: Start with two integers $p > q$. Compute the remainder $r₁ < q$ from $p = q + \ldots + r₁$. Note that $\gcd(p,q) = \gcd(q,r₁)$.

  2. Algorithm: Repeatedly divide the previous divisor by the current remainder:

    $$ r_{i-1} = r_i \cdot \dots + r_{i+1} \quad \gcd(r_{i-1}, r_i) = \gcd(r_i, r_{i+1}) $$

    The remainders form a strictly decreasing sequence of positive integers.

  3. Stop: The process ends when a remainder $rₙ₊₁$ becomes $0$. Then $\gcd(p,q) = r_{n'}$ the last non-zero remainder.

  4. Complexity: Each division costs $\mathcal O(L²)$ for $L$-bit integers. There are $\mathcal O(L)$ such divisions, giving total time $\mathcal O(L³)$.

✨ Theorem: Let $N$ a composite number and $y\in \{1, \cdots , N \}$ a solution of $y^2=1 \mod N$ with $y\ne 1 \mod N$ and $y\ne N-1 \mod N$ then $\gcd (y-1,N)$ and $\gcd(y+1,N)$ are non-trivial factors of $N$ which can be computed in $\mathcal O (\lceil \log N \rceil ^3)$ operations

🧚‍♂️ Proof: Since $y^2=1+Nk$ for some integer $k$ it follows that $N$ has a common factor with $y-1$ or with $y+1$.

However $1<y<N-1$ implies $y-1<y+1<N$ so that $N$ itself cannot be the common factor.

We therefore use Euclid’s algorithm in $\mathcal O (\lceil \log N \rceil ^3)$ operations to find $\gcd (y-1,N)$ and $\gcd(y+1,N)$ which are non-trivial factors of $N$

✨ Theorem: Let $N=p_1^{n_1}\cdots p_m ^{n_m}$ be the time factorization of the composite odd integer $N$. Let $x$ be a random chosen integer in the range $1\le x \le N$ subject to the condition that $x$ and $N$ are co-prime. if $r$ is the order of $x \mod N$

$$ p(r\;\text{is even and} \; x^{r/2} \ne -1 \mod N ) \ge 1-1/2^m $$

Shor’s quantum factoring algorithm

💼 Case: suppose $L$ bit composite odd integer $N$ is given

  1. Randomly choose $x$ with $1 \le x \le N-1$
  2. if $\gcd(x,N)>1$ then return $\gcd(x,N)$
  3. if $\gcd (x,N)=1$ use the order finding algorithm to find the order $r$ of $x \mod N$
  4. if $r$ is odd or if $r$ is even and $x^{r/2}=-1 \mod N$ return to $1.$
  5. Compute and return $\gcd (x^{r/2}-1,N)$ and $\gcd (x^{r/2}+1,N)$ using Euclid

💎 Conclusion: the complexity is $\mathcal O (L^4)$