Cryptography Reference
In-Depth Information
Exercise 2.46
Give an algorithm to solve the equation
x
2
≡
(
)
when
n
is
the product of two distinct primes and
a
is a quadratic residue modulo
n
.(Hint:Use
Tonelli's algorithm and the Chinese remainder theorem.)
a
mod
n