II Республиканская олимпиада по криптологии

1. Упростим основание по модулю 25:
\( 88 = 3 \cdot 25 + 13 \equiv 13 \pmod{25} \).
2. Воспользуемся теоремой Эйлера. Так как \( \text{НОД}(13, 25) = 1 \), имеем \( 13^{\phi(25)} \equiv 1 \pmod{25} \).
Вычислим функцию Эйлера: \( \phi(25) = 25 \left(1 - \frac{1}{5}\right) = 20 \).
Следовательно, \( 13^{20} \equiv 1 \pmod{25} \).
3. Разложим показатель степени 1986 по модулю 20:
\( 1986 = 20 \cdot 99 + 6 \).
Отсюда \( 13^{1986} \equiv 13^6 \pmod{25} \).
4. Вычислим \( 13^6 \pmod{25} \):
\( 13^2 = 169 = 6 \cdot 25 + 19 \equiv 19 \equiv -6 \pmod{25} \).
\( 13^6 = (13^2)^3 \equiv (-6)^3 = -216 \pmod{25} \).
\( -216 \div 25 = -9 \) (остаток 9), так как \( -216 = 25 \cdot (-9) + 9 \).
5. Переведем полученный остаток 9 в пятеричную систему счисления:
\( 9 = 1 \cdot 5^1 + 4 \cdot 5^0 = 14_5 \).

1. Определим вероятность правильного восстановления \( P \). Согласно правилу большинства, ошибка не происходит в двух случаях:
— Если ни один из трех бит не искажен: \( (1-p)^3 \).
— Если искажен ровно один бит из трех (выбираем 1 бит из 3): \( \binom{3}{1} p (1-p)^2 = 3p(1-p)^2 \).
Суммируем вероятности:
2. Сравним эффективность с одиночной передачей, где вероятность успеха равна \( 1-p \). Условие эффективности: \( P > 1-p \).
Так как по условию \( 0 < p < 1/2 \), то множители \( p \), \( (1-p) \) и \( (1-2p) \) всегда положительны. Следовательно, неравенство выполняется на всем заданном интервале.

Официальное решение:
1. Анализ вида функции: Заданные свойства определяют, как переменные входят в линейную часть функции (через операцию XOR — \(\oplus\)):
• По 1-му свойству переменные \(x_{1}\) и \(x_{4}\) входят в функцию \(f\) только в первой степени. Действительно, пусть \(f = x_{1} g \oplus h\), где \(h\) — часть функции \(f\), не зависящая от \(x_{1}\). Если переменную \(x_{1}\) инвертировать (т.е. \(x_{1} \oplus 1\)), то значение функции \(f\) изменится, и выполняется равенство \((x_{1} \oplus 1) g \oplus h = x_{1} \cdot g \oplus h \oplus 1\). Из этого уравнения следует, что \(g = 1\). Для переменной \(x_{4}\) — аналогично.
• По 2-му свойству в XOR-сумме участвует только одна из переменных \(x_{2}\) или \(x_{3}\) (если бы входили обе, то \(1 \oplus 1 = 0\), и при их одновременном изменении значение функции не изменилось бы).
• Общий вид: \(f = x_{1} \oplus x_{i} \oplus x_{4} \oplus \alpha \cdot x_{2} \cdot x_{3}\), где \(i \in \{2,3\}, \alpha \in \{0,1\}\).

2. Определение параметров по последовательности: Дан отрезок:
\(s_{1} = 0, s_{2} = 0, s_{3} = 1, s_{4} = 1, s_{5} = 0, s_{6} = 1\).
• Для \(s_{5}\): \(f(s_{1},s_{2},s_{3},s_{4}) = f(0,0,1,1) = 0\).
• Для \(s_{6}\): \(f(s_{2},s_{3},s_{4},s_{5}) = f(0,1,1,0) = 1\).
a) Если \(i=2\), то \(f = x_{1} \oplus x_{2} \oplus x_{4} \oplus \alpha \cdot x_{2} \cdot x_{3}\). Тогда для \(s_{5}\): \(0 \oplus 0 \oplus 1 \oplus \alpha \cdot 0 \cdot 1 = 1\). Но по условию \(s_{5} = 0\), значит, в этом случае приходим к противоречию.
b) Если \(i=3\), то \(f = x_{1} \oplus x_{3} \oplus x_{4} \oplus \alpha \cdot x_{2} \cdot x_{3}\). Подставляем заданные числа:
• \(s_{5} = s_{1} \oplus s_{3} \oplus s_{4} \oplus \alpha \cdot s_{2} \cdot s_{3} = 0 \oplus 1 \oplus 1 \oplus \alpha \cdot 0 \cdot 1 = 0\). Условие выполняется.
• \(s_{6} = s_{2} \oplus s_{4} \oplus s_{5} \oplus \alpha \cdot s_{3} \cdot s_{4} = 0 \oplus 1 \oplus 0 \oplus \alpha \cdot 1 \cdot 1 = 1 \oplus \alpha\). Но по условию \(s_{6} = 1\), откуда следует \(\alpha = 0\). Таким образом, \(f = x_{1} \oplus x_{i} \oplus x_{4}\).
Закон генерации: \(s_{k+4} = s_{k} \oplus s_{k+2} \oplus s_{k+3}\).

3. Вычисление:
• \(s_{7} = f(s_{3},s_{4},s_{5},s_{6}) = f(1,1,0,1) = 1 \oplus 0 \oplus 1 = \mathbf{0}\).
• \(s_{8} = f(s_{4},s_{5},s_{6},s_{7}) = f(1,0,1,0) = 1 \oplus 1 \oplus 0 = \mathbf{0}\).
Функция является линейной, так как не содержит произведений переменных.

Для решения воспользуемся принципом включений-исключений:
\( N(A \cup B \cup C) = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C| \).

1. Вычислим мощности множеств:
— \( |A| \): вид \( 00xxxx \), \( 2^4 = 16 \) ключей.
— \( |B| \): вид \( xxxx11 \), \( 2^4 = 16 \) ключей.
— \( |C| \): число способов выбрать 6 позиции для 4 единиц — \( \binom{6}{4} = 15 \).

2. Вычислим попарные пересечения:
— \( |A \cap B| \): вид \( 00xx11 \), \( 2^2 = 4 \) ключа.
— \( |A \cap C| \): вид \( 00xxxx \) с 4 единицами. Единственный вариант — \( 001111 \), \( 1 \) ключ.
— \( |B \cap C| \): вид \( xxxx11 \) с 4 единицами. В первых 4 позициях должно быть 2 единицы — \( \binom{4}{2} = 6 \) ключей.

3. Вычислим тройное пересечение:
— \( |A \cap B \cap C| \): вид \( 00xx11 \) с 4 единицами. Только \( 001111 \), \( 1 \) ключ.

4. Итоговый расчет:
\( N = 16 + 16 + 15 - (4 + 1 + 6) + 1 = 47 - 11 + 1 = 37 \).

1. Доказательство того, что 2 — квадратичный вычет:
Используем критерий для символа Лежандра \( (\frac{2}{p}) \): число 2 является вычетом тогда и только тогда, когда \( p \equiv 1 \) или \( 7 \pmod 8 \).
Вычислим \( 8191 \pmod 8 \):
\( 8191 = 8000 + 160 + 24 + 7 \equiv 7 \pmod 8 \).
Условие выполняется, значит \( (\frac{2}{p}) = 1 \).

2. Нахождение корня \( x \):
Заметим, что \( p = 8191 = 4 \cdot 2047 + 3 \), то есть \( p \equiv 3 \pmod 4 \).
Для таких чисел существует прямая формула извлечения корня:
Подставим значения: \( a = 2 \), \( p = 8191 \).
\( x = 2^{\frac{8191+1}{4}} = 2^{\frac{8192}{4}} = 2^{2048} \pmod{8191} \).

3. Упрощение вычислений:
Так как \( p = 2^{13}-1 \), то по определению модуля имеем \( 2^{13} \equiv 1 \pmod{8191} \).
Разделим показатель 2048 на 13:
\( 2048 = 13 \cdot 157 + 7 \).
Тогда:
Проверка: \( 128^2 = (2^7)^2 = 2^{14} = 2^{13} \cdot 2 \equiv 1 \cdot 2 = 2 \pmod{8191} \).