Многочлены Диксона: Как перемешать алфавит без коллизий. Представьте, что мы пишем свой шифр. У нас есть алфавит. Для удобства работы с криптографией возьмем алфавит, размер (мощность) которого равен простому числу . Пусть это будет p = 7. Наш алфавит: числа от 0 до 6. Нам нужна функция замены f(x). Если мы возьмем что-то простое, вроде f(x) = x^2 mod 7, нас ждет катастрофа: 2^2 mod 7 = 4 5^2 mod 7 = 4 Коллизия! И двойка, и пятерка превратились в четверку. При расшифровке мы не сможем узнать исходное число. Нам нужна формула, которая работает как идеальная биекция (1:1), где каждому входу соответствует уникальный выход. На сцену выходит Леонард Диксон В начале XX века математик Леонард Юджин Диксон описал семейство многочленов, которые при определенных условиях становятся перестановочными многочленами (Permutation Polynomials) над конечными полями. Это именно то, что нам нужно: они перемешивают данные, математически гарантируя от...