# 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](https://www.youtube.com/watch?v=lvTqbM5Dq4Q)