Многочлены Диксона: Как перемешать алфавит без коллизий. Представьте, что мы пишем свой шифр. У нас есть алфавит. Для удобства работы с криптографией возьмем алфавит, размер (мощность) которого равен простому числу . Пусть это будет 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) над конечными полями. Это именно то, что нам нужно: они перемешивают данные, математически гарантируя от...

Разрешенные уровни и код стабильности: Как алгоритм AKS приручил простые числа. Мы прошли путь от понимания двоичных разрядов как энергетических уровней (см. тут ) до наблюдения за "фазовыми переходами" на границах степеней двойки (см. тут ). Теперь пришло время задать главный вопрос: если мир простых чисел полон запретов, существует ли универсальный способ найти разрешенные состояния ? Можно ли вычислить стабильный "атом" простого числа, не перебирая все варианты? Интерференция разрешенных коридоров Как мы уже выяснили, простое число — это результат наложения множества условий. Каждое составное число (делитель) создает свою "волну запретов" в двоичном коде. Чтобы число оказалось простым, оно должно попасть в узкий разрешенный коридор , где все эти волны проходят через "ноль". Долгое время математики считали, что эти коридоры распределены почти хаотично. Поиск простого числа напоминал попытку найти иголку в стоге сена, г...