Problem 182

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 = me mod n. However, some messages are unconcealed, i.e. there exist messages m such that me 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:

real 0m2.067s user 0m2.034s sys 0m0.032s