|
Закрыть
Задачу "[[name]]" решило [[solved]] человек(а).
Вы решили задачу
и добавили [[value]] баллов к своей силе.
но задача по силе не входит в топ 100 решенных вами задач.
Вы не решили задачу.
За решение задачи можете добавить [[future]] баллов к силе.
[[formula]]
Сила пересчитывается один раз в сутки.
Сила задачи высчитывается по формуле: F=(B-D)/(1+[S/10]),
-
B - количество баллов за задачу, по умолчанию 100
-
D - штраф за попытку, по умолчанию 5
-
S - количество решивших данную задачу
Сила конкретного пользователя считается по 100 решенным задачам с максимальным значением силы.
|
Задачи: Информатика
|
|
Пожалуйста, не пишите нам, что вы не можете решить задачу.
Если вы не можете ее решить, значит вы не можете ее решить :-)
1
Задачу решили:
10
всего попыток:
20
Задача опубликована:
26.12.10 00:13
Источник:
Проект "Эйлер" (http://projecteuler.net)
Вес:
1
сложность:
3
баллы: 100
|
Сообщение в системе шифрования RSA представляет собой некоторое число m. Если необходимо зашифровать текст, сначала его каким-то известным образом превращают в число, а затем происходит собственно шифрование.
Шифрование осуществляется следующим образом:
- Выбирают два различных простых числа p и q.
- Вычисляют n=pq и φ=(p-1)(q-1). Число n должно быть достаточно велико, чтобы сообщения m попадали в интервал [0,n-1].
- Выбирают целое число e, 1<e<φ, не имеющее общих делителей с φ (gcd(e,φ)=1).
- Из числа m получают зашифрованное сообщение c=me mod n (здесь a mod b означает остаток от деления a на b).
Чтобы расшифровать текст, действуют следующим образом:
- Находят число d такое, что ed=1 mod φ
- Для зашифрованного сообщения c, вычисляют m=cd mod n.
Однако иногда попадаются такие неудачные сочетания e и m, что me mod n=m. Будем называть такие сообщения нескрытыми. Необходимо выбирать e таким образом, чтобы нескрытых сообщений было меньше. Например, пусть p=19 и q=37. Тогда n=19*37=703, и φ=18*36=648. Если мы выберем e=181, абсолютно все сообщения m (0≤m≤n-1) окажутся нескрытыми, хотя условие gcd(181,648)=1 выполняется. Такой выбор крайне неудачен. К сожалению, для любого e, выбранного согласно указанным правилам, всегда найдется сколько-то нескрытых сообщений. Возьмем p=1009 и q=3643. Найдите количество таких e, 1<e<φ(1009,3643), gcd(e,φ)=1, для которых количество нескрытих сообщений минимально.
Внимание! Если Вы увидите ошибку на нашем сайте, выделите её и нажмите Ctrl+Enter.
|
|