We’re pretty sure that classical computers can’t break RSA (because it is hard to factor large numbers on them), but we know tha
t quantum computers theoretically could. In this question, we will prove a fact that is a key part of Shor’s Algorithm, a quantum algorithm for factoring large numbers quickly1 . Let N = pq where p,q are primes throughout this question. (a) Prove that, for all a ∈ N, there are only four possible values for gcd(a,N). (b) Using part (a), prove that, if r 2 ≡ 1 mod N and r 6≡ ±1 (mod N) (i.e. r is a "nontrivial square root of 1" mod N), then gcd(r −1,N) is one of the prime factors of N. Hint: r2 = 1 mod N can be rewritten as r2 −1 = 0 mod N or (r +1)(r −1) = 0 mod N.
1 answer:
You might be interested in