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:
“Mark you the floore? that square & speckled stone,
Which looks so firm and strong,
Is Patience:”
—George Herbert (1593–1633)
“Though of erect nature, man is far above the plants. For man’s superior part, his head, is turned toward the superior part of the world, and his inferior part is turned toward the inferior world; and therefore he is perfectly disposed as to the general situation of his body. Plants have the superior part turned towards the lower world, since their roots correspond to the mouth, and their inferior parts towards the upper world.”
—Thomas Aquinas (c. 1225–1274)