Rabin Cryptosystem - Computing Square Roots

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.