Для шифрования передаваемых сообщений Катя и Юра используют следующий способ.

Question

Юра заранее выбрал набор коэффициентов (3, 6, 11, 22), натуральное число u и сообщил их Кате. Для шифрования сообщения (x1,x2,x3,x4), состоящего из нулей и единиц, Катя вычисляет сумму S=3x1+6x2+11x3+22x4, а затем находит остаток S’ от деления произведения Su на 43 и отсылает S’ Юре. Помогите Юре расшифровать сообщение S’ = 27, то есть найти соответствующую ему строку (x1,x2,x3,x4), если известно, что остаток от деления числа 6u на 43 равен 1.В ответе укажите последовательность из нулей и единиц, например: 0111

Вячеслав Шишкин · Accepted Answer

Начинаем с конца. 6u mod 43 =1 следовательно 6u=44, 87, 130,173,216..(43*n+1) 
Первое число из этого списка, которое делится без остатка на 6 = 216 поэтому предполагаем u=36 
 
Далее N*36 mod 43=27 отсюда (я лично перебором) получаем n=33. А вообще можно посчитать по методу китайской задачи об остатках. 
 
S=33 соответствует сумме 22+11 или сообщению 0011