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

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


Для того, чтобы сохранилась связь при выходе из строя любых двух узлов, необходимо, чтобы в каждый узел входило не менее трех линий связи. Ситуация

недопустима, ибо при выходе из строя узлов и узел становится недоступным. Значит, всего линий должно быть не менее

.

Вот два примера, удовлетворяющие условиям задачи с 15-ю линиями связи:

Приведем доказательство для первого примера. Если вышли из строя два узла на одном пятиугольнике, то связь сохранится через другие пятиугольники. Если вышли из строя по одному узлу на разных пятиугольниках, то связь сохранится по линиям, соединяющим эти пятиугольники.

Ответ: 15.

Процедура зашифрования может быть полностью описана квадратной таблицей . На пересечении строки с номером и столбца с номером записываем цифру, в которую при зашифровании переходит цифра , если она стоит в пароле после цифры . Из однозначности расшифрования следует, что в каждой строке каждая цифра встречается ровно один раз.

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

0 1 2 3 4 5 6 7 8 9

0

5

1

3

2

4 3 7 8

3

7

4

2

5

3

6

7

4

8

1 9

9

0 1 2 3 4 5 6 7 8 9

0

6 5

1

3

2

4 3 7 0 6 2 5 8 9

3

3 7

4

2

5

3 7

6

7

4

8

1 9

9

1

Очевидно, что в строке с номером 2 в последней клетке стоит 1. Знание этой таблицы позволяет однозначно расшифровать : получится 5830829. Пароли, соответствующие , , , , восстанавливаются не полностью.




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


[an error occurred while processing this directive]