Архив задач олимпиады по математике и криптографии
Переписка Кати и Юры
Для шифрования передаваемых сообщений Катя и Юра используют следующий способ. Юра заранее выбрал набор коэффициентов (2, 5, 8, 16), натуральное число u и сообщил их Кате. Для шифрования сообщения (x1,x2,x3,x4), состоящего из нулей и единиц, Катя вычисляет сумму S = 2x1 + +5x2+ 8x3 + 16x4, а затем находит остаток S′ от деления произведения Su на 32 и отсылает S′ Юре. Помогите Юре расшифровать сообщение S′ = 11, то есть найти соответствующую ему строку (x1,x2,x3,x4) , если известно, что остаток от деления числа 7u на 32 равен 1.
Обозначим через rM(b) - остаток от деления числа b на M. Запишем чему равно число S′ согласно определению деления натуральных чисел с остатком:
Поскольку известно, что остаток от деления 7u на M равен 1, то запишем:
Домножим обе части (1) на 7 и подставим в полученное равенство вместо 7u равенство (2). Имеем:
Заметим далее, что натуральное число
Поэтому полученное равенство (3) есть не что иное, как деление 7S′ с остатком на M и, кроме того, rM( 7S′) = S. Таким образом, найдя остаток от деления 7S′ на M , получим исходное число S.
В нашем случае, Теперь, зная S, осталось найти (x1,x2,x3,x4). Но это делается легко. Действительно, равенство x4 = 0 очевидно, поскольку S < 16. Дальше можно перебрать все возможные восемь вариантов, либо сразу заметить, что x2= x3 = 1, x1 = 0(что просто угадывается), либо последовательно вычитать из S числа a3,a2,a1 пока не получим нуль, полагая при этом, что соответствующий xi = 1.
