2012-05-06

Project Euler problem 182 - Solved

Comments

The statement of the problem can be found here.

In this problem we are given two primes p and q that are used to generate an n for an RSA key-pair.

As it states to complete a key pair one must choose an exponent e in the range but for each e there will be a number of unconcealed messages, this means that .

The number of unconcealed messages for an exponent e in modulo N with is equal to

Knowing this it is pretty easy to write a code that finds the exponents that generate the fewer unconcealed messages and add them up. The python source code can be downloaded (problem182.py):

import gmpy

if __name__ == '__main__':
    p = 1009
    q = 3643
    n = p * q
    phi_n = n - p - q + 1
    result = 0
    min_res = 9999999999999
    for e in range(1, phi_n):
        if gmpy.gcd(e, phi_n) != 1:
            continue
        num_unconcealed = (gmpy.gcd(e-1, p-1) + 1) * (gmpy.gcd(e-1, q-1) + 1)
        if num_unconcealed < min_res:
            min_res = num_unconcealed
            result = e
        elif num_unconcealed == min_res:
            result += e
    print("The result is: {0}".format(result))
comments powered by Disqus