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)
“To the young mind, every thing is individual, stands by itself. By and by, it finds how to join two things, and see in them one nature; then three, then three thousand; and so, tyrannized over by its own unifying instinct, it goes on tying things together, diminishing anomalies, discovering roots running underground, whereby contrary and remote things cohere, and flower out from one stem.”
—Ralph Waldo Emerson (1803–1882)