# Project Euler Problem 182 - Solved

Solution to ProjectEuler's problem 182 in Python using a straight-forward approach together with public key cryptography properties.

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 \( 1 < e < \phi(N) \) but for each *e* there will be a number of unconcealed messages, this means that \( m^{e} \equiv m \mod N \).

The number of unconcealed messages for an exponent *e* in modulo N with \( N = p * q \) is equal to \( (gcd(e-1, p-1) + 1) * (gcd(e-1, q-1) + 1) \)

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 Talkyard.