Введение в криптографию



...К задачам первой олимпиады


Все клетки квадрата размера разобьем на непересекающиеся группы по четыре клетки в каждой.

1 2 3 4 5 1
5 6 7 8 6 2
4 8 9 9 7 3
3 7 9 9 8 4
2 6 8 7 6 5
1 5 4 3 2 1

Отнесем клетки к одной и той же группе, если при каждом повороте квадрата до его самосовмещения они перемещаются на места клеток этой же группы. На рисунке показано такое разбиение на группы всех клеток квадрата , причем клетки одной группы помечены одной и той же цифрой. Всего таких групп будет  (целое, так как  - четное число). При наложении трафарета на квадрат ровно одна клетка из каждой группы окажется под его вырезами. Каждому трафарету поставим в соответствие упорядоченный набор всех клеток из таких групп, оказавшихся под вырезами трафарета при наложении его на квадрат помеченной стороной вверх. Такое соответствие является взаимнооднозначным, поскольку каждому ключу будет однозначно соответствовать упорядоченный набор из клеток (по одной из каждой группы), вырезанных в трафарете, и наоборот. Всего таких наборов . В самом деле, существует ровно четыре различных варианта выбора клетки из каждой группы независимо от выбранных клеток из других таких групп. Таким образом, число различных ключей шифра ``поворотная решетка'' при четных значениях  равно .

Легко видеть, что . Отсюда , где  - корни многочлена . Получаем

Буква ш.с. Ф В М Е Ж Т И В Ф Ю

Номер

22 3 14 7 8 20 10 3 22 32

Номер 20 1 12 5 6 18 8 1 20 30

Буква о.с.

Т А К Д Е Р Ж А Т Ь

Ответ: ТАКДЕРЖАТЬ

Ответ: начиная с 54.

Разложим числа и на простые множители: ;

. Обозначим буквой число , равное произведению . Найдем все его делители вида:

, где числа , , и принимают только значения 0 и 1. Тогда, как нетрудно видеть, числа и окажутся взаимно простыми. Полагая и , получим все искомые пары . В самом деле, в указанных выше условиях наибольший общий делитель такой пары равен , а ее наименьшее общее кратное равно . Таким образом, искомое число упорядоченных пар совпадает с числом всех делителей вида: , которое равно числу всех упорядоченных наборов длины 4 и состоящих только из 0 и 1. Число всех таких наборов равно , так как для каждого места в наборах существует ровно 2 варианта его значений независимо от значений на других местах. В общем случае число представляется в виде , где ,,..., - различные простые числа, а ,,..., - натуральные числа. Число всех делителей вида:




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