That is, unlike the RSA system, if you can decrypt messages encrypted by the Rabin function, you can also figure out the prime factors used in the modulus. How this works should be clear once we go over the proof of why the Rabin function is equivalent to factoring. Here's where some simple number theory kicks in. This observation was originally due to M. O. Rabin.
Decryption is simply root extraction.
Suppose algorithm A finds square roots mod pq . The only operations used are the arithmetic operations and gcd , all of which are polynomial time. This shows that if one can decrypt a message sent using Rabin's function, then one can also factor products of two primes efficiently. Since factoring is believed to be hard, so decrypting messages must also be difficult. Copyright 2001 Bennet Yee.