Введение в криптографию
[an error occurred while processing this directive]

...К задачам шестой олимпиады - часть 2


/p>

Искомый шифртекст: 515355128523864354

б) Пусть  - количество одношаговых поворотов I колеса от начала до остановки с номером , ,

 - цифра, на которую указывает стрелка II колеса в момент остановки с номером ,

 - цифра III колеса, на которую указывает стрелка III колеса в момент остановки с номером .

Тогда, учитывая, что начальное положение стрелок соответствует букве А на первом колесе и 0 на II и III колесах, справедливы равенства

для подходящих неотрицательных целых чисел и .

Заметим, что . Отсюда справедливы равенства

Подставляя эти значения в равенства () и (), получим

Следовательно,

Правая и левая части делятся на 70, то есть имеют вид для подходящего неотрицательного целого . Поэтому

Подставляя в (), получим

Учитывая условие I колеса, имеем

k 1 2 3 4 5 6 7

2 8 9 8 9 1 1

4 0 2 3 1 2 1

18 42 51 52 71 79 99

Буквы

C И С Т Е М А

Указание. Рассмотрим некоторую расстановку ненулевых цифр на окружности. Упорядоченную пару соседних цифр на этой окружности назовем 1-соседней, если является соседней с по часовой стрелке. Пару назовем 2-соседней, если существует цифра , для которой пары и являются 1-соседними.

Каждой расстановке ненулевых цифр на окружности однозначно соответствует цепочка 1-соседних пар вида: , , , ..., , , которой, в свою очередь, однозначно соответствует цепочка 2-соседних пар вида:

где и при .

Если из цепочки удалить любую пару, то по оставшимся парам она восстанавливается однозначно.

Если из цепочки удалить две соседние пары, то она также восстанавливается однозначно.

Удаление из любых трех пар приводит к неоднозначности восстановления цепочки . В этом можно убедиться, рассмотрев следующие фрагменты цепочки вида :

Таким образом, при наличии двух указанных в условии задачи цифровых текстов нам будут известны некоторые 2-соседние пары, в которых первая цифра берется из первой криптограммы, а вторая - из второй. Поэтому с учетом вышесказанного получаем условие однозначного восстановления порядка расстановки цифр на данной окружности.




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]