Computing Square Roots
The decryption requires to compute square roots of the ciphertext c modulo the primes p and q. Choosing allows to compute square roots by
and
- .
We can show that this method works for p as follows. First implies that (p+1)/4 is an integer. The assumption is trivial for c≡0 (mod p). Thus we may assume that p does not divide c. Then
where is a Legendre symbol. From follows that . Thus c is a quadratic residue modulo p. Hence and therefore
The relation is not a requirement because square roots modulo other primes can be computed too. E.g. Rabin proposes to find the square roots modulo primes by using a special case of Berlekamp's algorithm.
Read more about this topic: Rabin Cryptosystem
Famous quotes containing the words square and/or roots:
“In old times people used to try and square the circle; now they try and devise schemes for satisfying the Irish nation.”
—Samuel Butler (1835–1902)
“If the national security is involved, anything goes. There are no rules. There are people so lacking in roots about what is proper and what is improper that they don’t know there’s anything wrong in breaking into the headquarters of the opposition party.”
—Helen Gahagan Douglas (1900–1980)