Square roots in modular arithmetic [on hold]
Suppose $n = pq$ with $p$ and $q$ both primes.
Suppose that $\gcd(a, pq) = 1$. Prove that if the equation $x^2 ß a \bmod
n$ has any solutions, then it has four solutions.
Suppose you had a machine that could find all four solutions for some
given $a$. How could you use this machine to factor $n$?
No comments:
Post a Comment