Quantum Computing & Cryptography

Quantum Computing & Cryptography
010000101110011010100111101101101110100110111111000010101000100110101001101110101101100010100111100000111111010010100001101000101011111111100010101100111111100000101011011110011010101101111111

Shor factoring (1994): breaking RSA

Quantum evaluation of `y^a mod N` for random y, and ALL `a` at once
Determine period r, mod N: y^r = 1, so (y^r/2 - 1)*(y^r/2 + 1) = 0 -> will share factor with N

Shor factoring (1994): breaking RSA Quantum evaluation of ya mod N for random y, and ALL a at once Determine period r, mod N: yr = 1, so (yr/2 - 1)*(yr/2 + 1) = 0 -> will share factor with N

Shor factoring (1994): breaking RSA

Quantum evaluation of `y^a mod N` for random y, and ALL `a` at once
Determine period r, mod N: y^r = 1, so (y^r/2 - 1)*(y^r/2 + 1) = 0 -> will share factor with N