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 the physicians had not their cassocks and their mules, if the doctors had not their square caps and their robes four times too wide, they would never had duped the world, which cannot resist so original an appearance.”
—Blaise Pascal (1623–1662)
“Sprung from the West,
He drank the valorous youth of a new world.
The strength of virgin forests braced his mind,
The hush of spacious prairies stilled his soul.
His words were oaks in acorns; and his thoughts
Were roots that firmly gript the granite truth.”
—Edwin Markham (1852–1940)