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:
“Rationalists, wearing square hats,
Think, in square rooms,
Looking at the floor,
Looking at the ceiling.
They confine themselves
To right-angled triangles.”
—Wallace Stevens (18791955)
“There is nothing but is related to us, nothing that does not interest us,kingdom, college, tree, horse, or iron show,the roots of all things are in man.”
—Ralph Waldo Emerson (18031882)