многочлены - Однозначное расшифрование

Здесь рассматривается остаток от деления не самого многочлена, а его значения в точке $%x$%.

Числа $%a$% и $%b$% можно заменить их остатками от деления на 10. Легко видеть, что если $%a$% чётно, то значениями функции будут только чётные остатки. Они для однозначной расшифровки не годятся. Также не годится число $%a=5$%. Остаются четыре варианта: $%a=1,3,7,9$%. Рассмотрим случай $%a=1$%, $%b=0$%. Подставляя в качестве $%x$% по порядку все цифры от 0 до 9 и беря остаток, можно убедиться в том, что получается следующий набор: 0, 1, 2, 9, 8, 5, 6, 7, 4, 3. Это перестановка цифр, что означает возможность однозначной расшифровки (просто по таблице).

Если теперь $%a=1$%, а $%b$% произвольно, то прибавление $%b$% к всем остаткам даёт их циклическую перестановку. Это значит, что любое $%b$% здесь подходит, и для расшифровки достаточно вычесть $%b$%.

Наконец, для чисел $%a=3,7,9$% легко проверить по таблице умножения, беря последнюю цифру, что домножение на $%a$% чисел списка от 0 до 9 даёт некоторую их перестановку. Это говорит о возможности однозначной расшифровки. Выглядит она просто: если домножали на 3, то для восстановления прообраза достаточно домножить на 7, так как $%3\cdot7$% оканчивается единицей. Домножение на 9 равноценно переходу от $%y$% к $%-y$%, то есть, например, цифра 6 перейдёт в -6, что эквивалентно 10-6=4.

Таким образом, для наличия однозначной расшифровки натуральное число $%a$% должно оканчиваться одной из цифр списка 1, 3, 7, 9, а $%b$% при этом может быть каким угодно.