RSABreaker

This problem statement uses HTML elements which will not appear properly when viewing from some plugins. Please view the statement in the applet.

One of the most famous techniques in computer science is that of RSA encryption. To use it, we begin by choosing positive integers, e, n, d, and m, with the following properties.

• 1. n is divisible by no perfect squares larger than 1.
• 2. m is equal to the number of positive integers less than n that share no prime factors with n.
• 3. e * d has a remainder of 1 when divided by m.

Then, given an integer a, between 0 and n-1 inclusive, we encrypt it as the remainder, again between 0 and n-1 inclusive, when a^e is divided by n. Similarly, we decrypt an integer b, between 0 and n-1 inclusive, as the remainder, between 0 and n-1 inclusive, when b^d is divided by n. Any kind of data can be decomposed as a list of such integers, and thus, any kind of data can be encrypted and decrypted in this way.

For example, suppose e = 3, n = 10, d = 3, and m = 4. As required,

• 1. n is divisible by no perfect squares larger than 1.
• 2. There are precisely m positive integers less than n that share no prime factors with n, namely {1,3,7,9}.
• 3. d*e = 9, which has a remainder of 1 when divided by m.

We can thus use these values for RSA encryption. For example, we would encrypt 7 as 3, since 7^e = 343, which has a remainder of 3 when divided by n. Then, we would decrypt 3 as 7, since 3^d = 27, which has a remainder of 7 when divided by n.

Suppose you want to allow people to send you encrypted messages that only you can read, but you have no way of meeting these people privately to agree upon a secret code. Remarkably, RSA encryption makes this possible. First of all, you choose e, n, d, and m satisfying the conditions described above. Then you announce the values of e and n, called the public key, to the entire world. Now, everybody has the information required to encrypt messages. To decrypt these messages, however, it is necessary to know d, called the private key, and only you know that. Other people could theoretically compute a legal value for d, given e and n, but nobody has found a practical method for doing this when n is large.

When n is smaller, however, it is significantly easier to determine a legal private key, and hence to break RSA encryption. Create a class RSABreaker that contains a method decrypt, which is given an int e, an int n, and an int b, representing a public key and an encrypted integer. The method should return the decrypted value of b, as described above.