Архив задач олимпиады по математике и криптографии

Сдвиг.

Пусть x = (x1, … , x8) - двоичный вектор длины 8. Обозначим xd - циклический сдвиг вектора x на d позиций вправо. Например, если x = (1,0,0,0,0,0,0,0), то x2 = (0,0,1,0,0,0,0,0). При этом считаем, что x0 = x. Под суммой векторов x=(x1, … , x4) и y=(y1, … , y4) будем понимать x + y = (x1 ⊕ y1, x2 ⊕ y2, x3 ⊕ y3, x4 ⊕ x4). Здесь ⊕ – стандартная операция сложения битов: 0 ⊕ 0 = 1 ⊕ 1 = 0, 0 ⊕ 1 = 1 ⊕ 0 = 1. Пусть x = v + v1 + v4. Найдите d1, … , dn такие, что при любом исходном векторе v выполняется равенство v = xd1 + … + xdn.

  • Решение

    • Решение

    Заметим, что xd+8n = xd для любого натурального числа n. Вектору x = (x1, … , x8) взаимно-однозначно соответствует многочлен x(t) = x1 + x2t + ⋯ + x7t6 + x8t7 . Тогда циклический сдвиг вектора x на d позиций вправо равносилен умножению многочлена x(t) на td и приведению степеней мономов по модулю 8. Вектору x = v + v1 + v4 соответствует многочлен x(t) = 1 + t + t4 . Таким образом, нахождение d1, … , dn таких, что xd1 + … + xdn равносильно нахождению многочлена v(t) = td1 + ⋯ + tdn со свойством x(t)v(t) = 1 (с учётом приведения степеней мономов по модулю 8). Найти многочлен v(t) можно методом неопределённых коэффициентов, но быстрее из следующего алгоритма: x(t) 2 = 1 + t + t8 = t 2 , x(t)4 = t4 , x(t)8 = t8 = 1. Следовательно, v(t) = x(t)7 = x(t) 3x(t)4 = (1 + t + t4 )t2 t4 = t2+ t6 + t7.
  • Ответ

    • Ответ

    v = x2+x6+x7