Карусель Фробениуса: нормальные базисы без перебора ✛ ✎

Стоит подать питание, и карусель Фробениуса приходит в движение: каждый элемент конечного поля переходит в своего q-го потомка, а координаты сдвигаются по кругу. Это действие — автоморфизм Фробениуса — описано ещё Гауссом в его арифметических изысканиях, но долгое время запустить карусель без заеданий удавалось лишь ценой перебора или матричных манипуляций.

Секрет плавного вращения — в правильной рассаде: нужно найти такой нормальный базис, чтобы автоморфизм просто переставлял его элементы по циклу. Авторы работы предлагают не перебирать билеты наугад, а сразу вычислить список всех бракованных мест. Для расширения степени n они строят семейство кандидатов $β_t$ = (θ − t)⁻¹ — это словно кабинки на платформе, и почти все они подходят.

Ядро метода — сверхбыстрое вычисление определителя циркулянтной матрицы с полиномиальными входами. Матрица сводится к характеристическому полиному в алгебре с базисом Грёбнера, а хитрый p-адический подъём обходит нули в знаменателях формул Леверье. Благодаря технике треугольных множеств и модулярной композиции весь расчёт занимает почти линейное время от размера входа — O_ϵ((n² log q)^{1+ϵ}) битовых операций. Для малых полей поле временно расширяют логарифмическим умножением, строят нормальный элемент там и аккуратно спускают обратно — и всё это детерминированно.

Карусель теперь запускается не с зажмуренными глазами, а с полным знанием безопасной точки старта. Это даёт криптографическим протоколам гарантированную стойкость, а системам компьютерной алгебры — воспроизводимость вычислений. Следующий шаг — ускорить проекцию в треугольном базисе до истинно линейного времени, и тогда общая сложность упадёт до O˜(n²). Когда-то Гаусс вращал числа вручную; сегодня алгоритмическая карусель делает это за миллисекунды, оставляя нам лишь восхищение чистой математикой.