# Problem 182 – RSA encryption

The 182nd Euler problem was definitely very interesting to solve. At first, the problem description looks very complicated and with a lot of information. But after some reading I was able to disregard some of the information. I will try to put my line of thoughts into words.

The RSA encryption is base on the following procedure:

- Generate two distinct primes
*p*and*q*. - Compute n = p q and phi = (p-1) (q-1).
- Find an integer e, 1 < e < phi, such that gcd(e,phi) = 1.

The *e* is used to encrypt a message. So, for a message *m*, we need to calculate c = m^{e} mod n. However, some messages are unconcealed, i.e. there exist messages *m* such that m^{e} mod n = m.

The problem aims to find the sum of all values of *e*, 1 < e < phi (1009,3643) and gcp(e,phi) = 1 so that the number of unconcealed messages is at a minimum.

As a starting point, phi is easily calculated:

phi = (p-1)*(q-1)

In the same way, the problem description describes the range of values in which one should pick *e*:

e <- [2..phi-1]

Until now it is easy. The big issue is how to find out how to make sure that the number of unconcealed messages is at a minimum. After some reading, I found out that the number of unconcealed messages is given by:

(1 + gcd (e-1) (p-1)) * (1 + gcd (e-1) (q-1))

Furthermore, it is also true (page 290 of Handbook of applied cryptography) that since *e-1*, *p-1* and *q-1* are all even, the number of unconcealed messages is always at least 9. So if we want to make sure that we sum the values of e so that the number of unconcealed messages are at a minimum:

(1 + gcd (e-1) (p-1)) * (1 + gcd (e-1) (q-1)) == 9

From this formula we can derive that in order to have 9 as a result:

(gcd (e-1) (p-1)) +1 == 3

and

(gcd (e-1) (q-1)) +1 == 3

Since now we have all the pieces of the puzzle, here is the complete solution:

f p q = let phi = (p-1)*(q-1) in sum [e | e <- [2..phi-1], gcd e phi == 1, (gcd (e-1) (p-1)) +1 == 3, (gcd (e-1) (q-1)) +1 == 3 ] main = print $ f 1009 3643

The execution is also quite fast, as you can see: