Тема Межрегиональная им. И. Я. Верченко (криптография)
Уравнения и системы на Верченко
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела межрегиональная им. и. я. верченко (криптография)
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#75003

Подписью битового сообщения (a,...,a )
 1     5  является любой битовый набор (x ,...,x ),
 1     10  при котором

pict

Здесь ⊕ — стандартная операция сложения битов: 0⊕ 0= 1⊕ 1= 0,0⊕ 1= 1⊕ 0= 1.

Найдите какую-нибудь подпись для сообщения (0,1,0,0,0).

Источники: Верченко-2022 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Мы понимаем, что складывая одинаковые переменные они уничтожаются, поэтому полезно поскладывать уравнения в этой системе, тем самым, упростив её.

Подсказка 4

Сложите первые 3 уравнения, используя полученные знания, сложите 4-ое и 5-ое уравнения.

Подсказка 5

Теперь мы можем перейти к настоящей пугающей части, но не спешим расстраиваться, ведь нам нужно найти какой-нибудь набор иксов, а значит мы можем дополнительно навесить на него удобные нам ограничения, и если получится найти набор с доп. ограничениями, то задача решена. Какие бы ограничения нам тогда наложить?

Подсказка 6

Давайте перейдём от квадратичной системы к линейной, зафиксировав значения (x7,x8,x9,x10)=(1,1,0,0), и попробуем решить систему попроще.

Подсказка 7

Не забываем, что помимо действий с уравнениями мы можем делать действия внутри уравнения, давайте избавимся от 1, добавив их к обеим частям. Посмотрите на уравнения 2,4 и 1,3, дальше уже можно найти решение и радоваться победе!

Показать ответ и решение

Для начала, используя (a,a ,a ,a,a )= (0,1,0,0,0),
 1  2 3  4 5  найдем b,b,b,b ,b .
1 2  3 4 5  Для этого решим систему:

( b ⊕ b ⊕b = 0
|||||  3   4  5
|{ b2⊕ b4⊕b5 = 1
||| b2⊕ b3⊕b5 = 0
|||( b1⊕ b2⊕b3 = 0
  b1⊕ b3⊕b5 = 0

Сложив первые три уравнения и преобразовав их, получаем b = 1.
 5  Подставим это значение в нашу систему:

(| b ⊕ b =1
||||| b3⊕ b4=0
{ b2⊕ b4=1
|||| b2⊕ b3⊕b = 0
||(  1   2  3
  b1⊕ b3 =1

Сложим четвертое и пятое уравнения и получим, что b2 = 1.  Тогда из второго уравнения следует, что b4 = 1,  а из третьего следует, что b3 = 0.  Тогда из пятого получаем b1 =1.

Итак, (b,b ,b ,b,b)= (1,1,0,1,1).
  1 2 3 4 5  Теперь нужно найти набор какой-нибудь (x ,x,x ,x ,x ,x ,x,x ,x,x ).
 1  2 3 4  5 6  7 8  9 10

Для этого найдем любое решение системы:

(| x x ⊕ x x ⊕ x x ⊕x x ⊕ xx  ⊕x x ⊕ xx ⊕ x x = 1
||||| x1x9⊕ x21x0⊕x 3x 8⊕x4x9⊕ x5x9 ⊕ 6x 8x ⊕7x8x ⊕9x 10x = 1
{ x1x8⊕ x29x ⊕ 3x 1x0⊕x4x8⊕ x5x10⊕x 6x10⊕ xx7⊕8x 8x 9⊕x  = 0
||||  1 9   210   3 8  4 7   58   6 8  7 8   8 9  10
||( x1x7⊕ x2x10⊕ x3x10⊕ x4x7⊕x5x7⊕ x6x10⊕ x7x10⊕ x9x10 =1
  x1x8⊕ x2x7 ⊕x3x7⊕ x4x9⊕ x5x9⊕x6x8⊕ x7x8 ⊕x8x10⊕x9 = 1

Решать квадратичную систему с десятью переменными сложно, поэтому попробуем ее как-нибудь упростить. Видно, что если убрать переменные x ,x ,x ,x ,
 7  8 9  10  то получится линейная система. Тогда зафиксируем значения этих переменных так, чтобы в новой системе не было противоречий, например, так: (x7,x8,x9,x10)= (1,1,0,0).  Тогда все слагаемые, в которых есть x9  или x10  пропадут.

После подстановки этих значений в систему получаем:

(
|||||  x3⊕ x6 ⊕1= 1
|{  x1⊕ x4 ⊕1= 1
|||  x3⊕ x4 ⊕x5⊕ x6⊕ 1= 0
|||(  x1⊕ x4 ⊕x5 = 1
   x1⊕ x2 ⊕x3⊕ x6⊕ 1= 1

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

(
||||| x3⊕ x6 = 0
|{ x1⊕ x4 = 0
||| x3⊕ x4⊕ x5 ⊕x6 = 1
|||( x1⊕ x4⊕ x5 =1
  x1⊕ x2⊕ x3 ⊕x6 = 0

Из второго и четвертого уравнений следует, что x = 1.
 5  Тогда из первого и третьего получаем, что x = 0.
 4  Теперь подставим эти значения в систему:

( x ⊕ x = 0
|||||  3   6
|{ x1 = 0
||| x3⊕ x6 = 0
|||( x1 = 0
  x1⊕ x2⊕ x3 ⊕x6 = 0

Итак, x1 = 0.  Тогда из первого и пятого получаем, что и x2 =0.  Осталось выбрать какие-нибудь значения для x3x6,  так как их система однозначно не задает. Пусть x = x = 0.
 3   6

Получаем следующую подпись: (0,0,0,0,1,0,1,1,0,0).

Ответ:

 (0,0,0,0,1,0,1,1,0,0)

Рулетка
Вы можете получить скидку в рулетке!