Архив задач олимпиады по математике и криптографии
Можно ли так шифровать?
Рассмотрим преобразование цифрового текста, в котором каждая цифра заменяется остатком от деления значения многочлена F(х)=b(x3+7x2+3x+a) на число 10, где a, b - фиксированные натуральные числа.
Выясните, при каких значениях a, b указанное преобразованиеможет быть шифрпреобразованием (т. е. допускает однозначное расшифрование).
Обозначим через f(x) - остаток от деления значения многочлена F(x) на 10. Для однозначного расшифрования необходимо и достаточно, чтобы разным значениям x соответствовали разные значения f(x). Поэтому f(0), f(1), ..., f(9) принимают все значения от 0 до 9. Найдем эти значения:
f(0) = r10(b(a+0))
f(1) = r10(b(a+1))
f(2) = r10(b(a+2))
f(3) = r10(b(a+9))
f(4) = r10(b(a+8))
f(5) = r10(b(a+5))
f(6) = r10(b(a+6))
f(7) = r10(b(a+7))
f(8) = r10(b(a+4))
f(9) = r10(b(a+3)),
где r10(y) - остаток от деления числа y на 10.
Отсюда, пользуясь свойствами остатков, замечаем, что b должно быть нечетным (иначе f(x) будут только четные числа) и b не должно делиться на 5 (иначе f(x) будут только 0 и 5). Непосредственной проверкой можно убедиться, что при любом a и при всех b, удовлетворяющим приведенным условиям, гарантируется однозначность расшифрования.