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:
“O for a man who is a man, and, as my neighbor says, has a bone in his back which you cannot pass your hand through! Our statistics are at fault: the population has been returned too large. How many men are there to a square thousand miles in this country? Hardly one.”
—Henry David Thoreau (1817–1862)
“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 (1803–1882)