Summary: Factoring Algorithm

Here are the key takeaways:

• Encryption employs a key $K$ that is typically used with other numbers to encode and decode the message. The RSA protocol for encryption involves factoring a product $N$ of two large prime numbers $p$ and $q$. It also uses the value of $d$ which satisfies:
  $1 = Kd \mod (p − 1)(q − 1)$.

• The prime factors, $p$ and $q$, and the number $d$ are kept secret. $K$ and $N$ may be shared publicly, and the sender uses them to encrypt the message. For large $N$, classical computers are unable to do the calculations fast enough to determine $p$, $q$, and $d$ in a practical amount of time.

• The Shor algorithm is a famous quantum algorithm that can find the encryption key faster by making use of the periodic nature of the remainder or $\text{mod}$ function. In effect, the Shor algorithm allows us to break the RSA encryption and other encryption methods based on factoring large numbers, the basis for a large portion of our internet security. The algorithm does this by making use of quantum Fourier transforms, which approximate periodic functions as a series of cosine and sine functions. The periods of the cosine and sine functions give information about the period of the original function.