Project Euler Problem 182

Statement

The RSA encryption is based on the following procedure:

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

A message in this system is a number in the interval [0,n-1].
A text to be encrypted is then somehow converted to messages (numbers in the interval [0,n-1]).
To encrypt the text, for each message, m, $c=m^e ~ mod ~ n$ is calculated.

To decrypt the text, the following procedure is needed: calculate d such that $ed=1 ~ mod~ \phi$, then for each encrypted message, c, calculate $m=c^d ~ mod ~ n$.

There exist values of e and m such that $m^e ~ mod ~ n=m$.
We call messages m for which $m^e ~ mod ~ n=m$ unconcealed messages.

An issue when choosing e is that there should not be too many unconcealed messages.
For instance, let p=19 and q=37.
Then $n=19*37=703$ and $\phi =18*36=648$.
If we choose e=181, then, although gcd(181,648)=1 it turns out that all possible messages
m $(0 < m < n-1)$ are unconcealed when calculating $m^e ~ mod ~ n$.
For any valid choice of e there exist some unconcealed messages.
It's important that the number of unconcealed messages is at a minimum.

Choose p=1009 and q=3643.
Find the sum of all values of e, $1 <e < \phi(1009,3643)$ and $gcd(e,\phi)=1$, so that the number of unconcealed messages for this value of e is at a minimum.

Solution

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:

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))

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License