Задача
Некоторый текст зашифровали, поставив в соответствие каждой букве некоторую (возможно, ту же самую букву) букву так, что текст можно однозначно расшифровать. Докажите, что найдется такое число N, что после N-кратного применения шифрования заведомо получится исходный текст. Найдите из всех таких значений N наименьшее, годящееся для всех шифров (при условии, что в алфавите 33 буквы). (Задача с сайтаwww.cryptography.ru.)
Решение
По условию шифрование допускает однозначную расшифровку. Это означает, что шифрование - это просто некоторая перестановка 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.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь