Задача 182
Шифрование методом RSA

Алгоритм шифрования RSA основывается на следующей процедуре:

Генерация двух различных простых чисел p и q.
Вычисление n=pq и φ=(p-1)(q-1).
Поиск целого числа e, 1<e<φ, такого, что НОД(e,φ)=1.

Сообщение в этой системе представлено в виде числа, принадлежащего интервалу [0,n-1].
Шифруемый текст каким-нибудь способом преобразовывается в такие сообщения (числа, принадлежащие интервалу [0,n-1]).
Чтобы зашифровать текст, для каждого сообщения m, необходимо вычислить c=m^(e) mod n.

Для дешифровки текста выполняется следующая процедура: найти такое d, чтобы ed=1 mod φ, затем для каждого зашифрованного сообщения c вычислить m=c^(d) mod n.

Существуют такие значения e и m, что m^(e) mod n=m.
Сообщения m, для которых m^(e) mod n=m, будем называть открытыми.

Проблема выбора e состоит в том, что не должно быть слишком много открытых сообщений.
К примеру, пусть p=19 и q=37.
Тогда n=19*37=703 и φ=18*36=648.
Если выберем e=181, то, несмотря на то, что НОД(181,648)=1, окажется, что все возможные сообщения
m (0≤m<n-1) будут открытыми после вычисления m^(e) mod n.
Для любого верного выбора e существуют некоторые открытые сообщения.
Важно, чтобы число таких открытых сообщений было минимальным.

Дано: p=1009 и q=3643.
Найдите сумму всех значений e, 1<e<φ(1009,3643) и НОД(e,φ)=1, для которых число открытых сообщений будет минимальным.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net