quantum/03_shors.md

High level overview of RSA and Shor's algo

RSA relies on:

N = p*q

where N is a big number and p and q are large prime number.

So, say we have N. Make a guess g. g doesn't have to be a factor of N, it can be a number that shares factors with N, e.g.

N = g * h

N = a * b  # 4 = 2 * 2
g = a * c  # 6 = 2 * 3
gcd(N, g) = a

g^(p/2) +- 1

A, B -> no common factors
A, B -> A^p = m*B + 1
7, 15 -> 7^2 = 3*15 + 1
         7^3 = 22*15 + 13
         160*15 + 1

Sources:

• Minute Physics - Quantum Crypto video