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:
“If magistrates had true justice, and if physicians had the true art of healing, they would have no occasion for square caps; the majesty of these sciences would of itself be venerable enough. But having only imaginary knowledge, they must employ those silly tools that strike the imagination with which they have to deal; and thereby, in fact, they inspire respect.”
—Blaise Pascal (1623–1662)
“Our roots are in the dark; the earth is our country. Why did we look up for blessing—instead of around, and down? What hope we have lies there. Not in the sky full of orbiting spy-eyes and weaponry, but in the earth we have looked down upon. Not from above, but from below. Not in the light that blinds, but in the dark that nourishes, where human beings grow human souls.”
—Ursula K. Le Guin (b. 1929)