Архив задач олимпиады по математике и криптографии
Ключи.
Имеется устройство, которое строит последовательность чисел x0, x1, x2, … следующим образом: первые два члена x0 и x1 мы задаем самостоятельно, а последующие члены устройство вычисляет так: x2 = x0 + 13 ⋅ (x1 + k1), x3 = x1 + 13 ⋅ (x2 + k2) , … Здесь k1, k2, … – некоторая фиксированная ключевая последовательность. При этом все числа x0, x1, x2, … и k1, k2, … являются целыми, лежащими в пределах от 0 до 32 включительно. (Если в процессе вычислений получится число, превосходящее 32, то результат будет заменен его остатком от деления на 33; например, 16 + 13 ⋅ 2 = 9.) С помощью этого устройства построили две последовательности a0, a1, a2, … и b0, b1, b2, …, по первым членам a0 = 1, a1 = 3 и b0 = 1, b1 = 12. Верно ли, что найдётся ключевая последовательность k1, k2, … и некоторое целое t, большее 0, такие, что выполняются условия: а) bt= at, bt+1 = at+1; б) bt= at+1? Решение обоснуйте.
a) Для всех t больше 0 at+1 = at−1 + 13(at + kt), at−1 = at−1 − 13(at−1 + kt). Поэтому, если bt+1= at+1 , bt= at, то bt−1 = at−1, bt−2 = at−2,… , b1 = a1, b0 = a0, что противоречит условию. б) Удобно перейти к разностям полублоков zt = bt − at (везде далее действия с полублоками (умножение, сложение и вычитание) производятся по модулю M) и выяснить, может ли 1 появиться в {zt}. Из уравнения шифрования получаем, что последовательность разностей: zt+1 = bt−1 + 13(bt + kt ) − (at−1 + 13(at + kt )) = zt−1 + 13zt ,t больше 0, не зависит от ключа. По условию (z0, z1) = (0, 9), (z0, z1, M) = 3, поэтому все члены последовательности будут делиться на 3, и единицы там не будет.