1         Bad RSA [25%]

In the text file we provide you with a RSA modulus n which has two prime factors p and q such that |p − q| < 10000. We provide you also with a public key e and a plain-RSA ciphertext y.

Decrypt y. Provide the decrypted plaintext.

(As the exercise that does state otherwise, this is textbook RSA, i.e., you encrypt numbers and decrypt numbers modulo n).

Explain your reasoning and code. The correctness as well as the efficiency of the solution matters.

Hint: Binary search.

SAGE is a free open-source maths software based on Python. You can find information about it at http://www.sagemath.org/.