2019-09-25 08:44:26 +02:00
|
|
|
# High level overview of RSA and Shor's algo
|
|
|
|
|
|
2019-09-25 08:14:41 +02:00
|
|
|
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
|
|
|
|
|
|
|
|
|
|
```
|
|
|
|
|
|
2019-09-25 08:44:26 +02:00
|
|
|
## Sources:
|
|
|
|
|
* [Minute Physics - Quantum Crypto video](https://www.youtube.com/watch?v=lvTqbM5Dq4Q)
|
