Peter Shor's Algorithm

The information in the web site (personal passwords, credit card's number, etc) is safety thanks to cryptography protocols which security is given by the complexity of solve problems as Factoring numbers. 

Factoring Number's Problem

Let $N\in \mathbb{N}$ be, then the problem consist on find $(a,b)\in \mathbb{N}^2$ such that $N=a*b$.

One could say find factors of a number is easy:

6=2*3

143=11*13

6319=n*m

What are the values n and m? Well, the problem is more complicated while we increase the number of digits of the number.

The problem of Factoring numbers has been studied for long time and there exists some algorithms to find the factoring of $N\in \mathbb{N}$, one of these is the Peter Shor's Algorithm.

Peter Shor's Algorithm

Let $N\in \mathbb{N}$.

1. Choose randomly $0<a<N$ integer.

2. Compute $g.c.d(a,N)$.

3.

    a) If $g.c.d(a,N)\neq 1$, then $g.c.d(a,N)$ is factor of $N$, then the algorithm is ended.

    b) If g.c.d(a,N) =1, then we have to find the period $T$ of the function $f(x)=a^x \ \mathrm{mod} \ N$.

4. 

    a) If T is odd, then do $a=T$ and back to step 2.

    b) If T is even and $a^{T/2} \equiv -1 \ \mathrm{mod} \ N$, do $a=T$ and back to step 2.

5. So, the algorithm end when $T$ is even and $a^{T/2} \not \equiv -1 \ \mathrm{mod} \ N$ and the factors of $N$ are given by 

$g.c.d(a^{T/2}-1,N)$ and $g.c.d(a^{T/2}+1,N)$

When the number to factoring is small, we can compute $T$ in step 2.b) using an usual computer, and in another case we use a sub-program based in qubits.

For example, to find the factoring of $N=6319$.

•  Choose $a=4489$ (other value could be better or maybe worse in sense speed to do computes).
• $g.c.d(4489,6319)=1$ and $T=385$ for $f(x)=4489^x \ \mathrm{mod} \ 6319$.
• Backing to step 2 and doing $a=385$. 
• $g.c.d(385,6319)=1$ and $T=616$ for $f(x)=385^x \ \mathrm{mod} \ 6319$.
• As $T$ is even and $385^{616/2} \not \equiv -1 \ \mathrm{mod} \ 6319$, factors for $N=6319$ are:

$g.c.d(385^{616/2}-1,6319)=71$   and   $g.c.d(385^{616/2}+1,6319)=89$

The implementation of Peter Shor's Algorithm means that factoring problem is easy to solve computationally. Also using versions of Peter Shor's Algorithm could be easy to solve the Discrete Logarithm Problem. Faced with the threat of the arrival of quantum computers have been developed classic schemes for whose the Peter Shor's Algorithm couldn't be applied effectively, these kind of schemes are called post-quantums schemes.