Условие
Некоторый текст зашифровали, поставив в соответствие каждой букве
некоторую (возможно, ту же самую букву) букву так, что текст можно
однозначно расшифровать. Докажите, что найдется такое число N, что
после N-кратного применения шифрования заведомо получится исходный
текст. Найдите из всех таких значений N наименьшее, годящееся для всех шифров (при условии,
что в алфавите 33 буквы).
(Задача с сайта
www.cryptography.ru.)
Подсказка
Если буква a
1 шифруется в букву a
2,
буква a
2 шифруется в букву a
3, ... ,
буква a
k шифруется в букву a
1, то
при k-кратном шифровании мы получим исходный текст.
Решение
По условию шифрование допускает однозначную расшифровку.
Это означает, что шифрование - это просто некоторая перестановка
33 букв алфавита, (т.е. в каждую из букв некоторая буква шифруется).
Пусть буква a
1 шифруется в букву a
2,
буква a
2 шифруется в букву a
3, и т.д. ,
буква a
k шифруется в букву a
k+1, ...
В последовательности букв
a
1, a
2, ... в некоторый момент возникнет
первое повторение, т.е. буква a
k+1 совпадет с одной из
букв a
1, a
2, ... , a
k, а буквы
a
1, a
2, ... , a
k - различны.
Но a
k+1 не может совпасть с одной из букв
a
2, ... , a
k, поскольку в них шифруются
соответственно
a
1, a
2, ... , a
k-1, а в
a
k+1 шифруется a
k.
Таким образом, a
k+1=a
1.
Итак, мы имеем следующий цикл:
a
1 шифруется в букву a
2,
буква a
2 шифруется в букву a
3, ... ,
буква a
k шифруется в букву a
1.
При k-кратном шифровании буквы
a
1, a
2, ... , a
k
будут стоять на тех же местах, как и в исходном тексте.
Вся перестановка букв тем самым разбилась на циклы.
Длина цикла может быть от 1 до 33.
Если взять N, делящееся на каждое из чисел
1, 2, ... , 33, и сделать N-кратное шифрование,
то буквы каждого цикла будут стоять на своих местах,
т.е. мы получим исходный текст.
Наоборот, если N не делится на одно из чисел k от 1 до 33,
то в случае, если шифрование содержит цикл длины k,
после N-кратного применения шифрования мы не получим исходный
текст. Итак, искомое число N - наименьшее общее кратное чисел 1,
2, ... , 33. Это число огромно, оно равно 144403552893600.
Ответ
наименьшее искомое число - 144403552893600.
Источники и прецеденты использования
|
|
|
web-сайт |
|
URL |
cryptography.ru |
|
Название |
Сайт "Криптография" |
|
задача |
