ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 35604
Темы:    [ Группа перестановок ]
[ Криптография ]
Сложность: 3+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Некоторый текст зашифровали, поставив в соответствие каждой букве некоторую (возможно, ту же самую букву) букву так, что текст можно однозначно расшифровать. Докажите, что найдется такое число N, что после N-кратного применения шифрования заведомо получится исходный текст. Найдите из всех таких значений N наименьшее, годящееся для всех шифров (при условии, что в алфавите 33 буквы). (Задача с сайта www.cryptography.ru.)

Подсказка

Если буква a1 шифруется в букву a2, буква a2 шифруется в букву a3, ... , буква ak шифруется в букву a1, то при k-кратном шифровании мы получим исходный текст.

Решение

По условию шифрование допускает однозначную расшифровку. Это означает, что шифрование - это просто некоторая перестановка 33 букв алфавита, (т.е. в каждую из букв некоторая буква шифруется). Пусть буква a1 шифруется в букву a2, буква a2 шифруется в букву a3, и т.д. , буква ak шифруется в букву ak+1, ... В последовательности букв a1, a2, ... в некоторый момент возникнет первое повторение, т.е. буква ak+1 совпадет с одной из букв a1, a2, ... , ak, а буквы a1, a2, ... , ak - различны. Но ak+1 не может совпасть с одной из букв a2, ... , ak, поскольку в них шифруются соответственно a1, a2, ... , ak-1, а в ak+1 шифруется ak. Таким образом, ak+1=a1. Итак, мы имеем следующий цикл: a1 шифруется в букву a2, буква a2 шифруется в букву a3, ... , буква ak шифруется в букву a1. При k-кратном шифровании буквы a1, a2, ... , ak будут стоять на тех же местах, как и в исходном тексте. Вся перестановка букв тем самым разбилась на циклы. Длина цикла может быть от 1 до 33. Если взять N, делящееся на каждое из чисел 1, 2, ... , 33, и сделать N-кратное шифрование, то буквы каждого цикла будут стоять на своих местах, т.е. мы получим исходный текст. Наоборот, если N не делится на одно из чисел k от 1 до 33, то в случае, если шифрование содержит цикл длины k, после N-кратного применения шифрования мы не получим исходный текст. Итак, искомое число N - наименьшее общее кратное чисел 1, 2, ... , 33. Это число огромно, оно равно 144403552893600.

Ответ

наименьшее искомое число - 144403552893600.

Источники и прецеденты использования

web-сайт
URL cryptography.ru
Название Сайт "Криптография"
задача

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .