Корни многочлена mod a prime

Question

Я ищу быстрый алгоритм для поиска корней одномерного многочлена в конечном конечном поле.

То есть, если f = a0 + a1x + a2x2 + ... + anxn (n> 0), то алгоритм, который находит все r < p, удовлетворяющие f(r) = 0 mod p, для заданного простого числа p.

Я нашел алгоритм поиска Chiens https://en.wikipedia.org/wiki/Chien_search, но я не могу представить, что это быстрое, для простых чисел более 20 бит. Кто-нибудь имеет опыт работы с алгоритмом поиска Чиена или знает более быстрый способ? Есть ли симплексный модуль для этого?

Answer 1

Это довольно хорошо изучено, как указывает комментарий mcdowella. Вот как работает Cantor-Zassenhaus random algorithm для случая, когда вы хотите найти корни полинома, а не более общую факторизацию. Заметим, что в кольце многочленов с коэффициентами mod p произведение x (x-1) (x-2) ... (x-p + 1) имеет все возможные корни и равно x^px по формуле (x-1) (x-2) ... (x-p + 1). Fermat's Little Theorem и уникальная факторизация в этом кольце.

Набор g = GCD (f, x^p-x). Использование Euclid's algorithm для вычисления GCD двух многочленов является быстрым в общем случае, беря несколько шагов, которые являются логарифмическими в максимальной степени. Это не требует, чтобы вы определяли многочлены. g имеет те же корни, что и f в поле, и не повторяющиеся факторы.

Из-за специальной формы х^рх с двумя отличными от нуля членами первый шаг алгоритма Евклида может быть выполнен с помощью repeated squaring, примерно в 2 log_2 (p) шагах с участием только многочленов степени не более чем в два раза степени f, с коэффициентами mod p. Мы можем вычислить x mod f, x^2 mod f, x^4 mod f и т. Д., А затем умножить числа, соответствующие ненулевым местам в двоичном разложении p, для вычисления x^p mod f и, наконец, вычесть x.

Неоднократно выполняйте следующее: выберите случайный d в Z/p. Вычислите GCD группы g с r_d = (x + d)^((p-1)/2) -1, который мы можем быстро вычислить по алгоритму Евклида, используя повторное возведение в квадрат на первом шаге. Если степень этого GCD строго находится между 0 и степенью g, мы нашли нетривиальный множитель g, и мы можем рекурсировать, пока не найдем линейные факторы, следовательно, корни из g и, следовательно, f.

Как часто это работает? r_d имеет в качестве корней числа, которые меньше d, чем ненулевой квадрат mod p. Рассмотрим два разных корня из g, a и b, поэтому (x-a) и (x-b) являются факторами g. Если a + d - ненулевой квадрат, а b + d - нет, то (xa) является общим фактором g и r_d, тогда как (xb) нет, что означает, что GCD (g, r_d) является нетривиальным фактором g , Аналогично, если b + d является ненулевым квадратом, а a + d - нет, то (x-b) является общим фактором g и r_d, а (x-a) - нет. По теории чисел один случай или другой случай близок к половине возможных вариантов для d, а это означает, что в среднем он принимает постоянное количество вариантов d до того, как найдет нетривиальный множитель g, фактически одно разделяющее (xa) из (xb).

Answer 2

Ваши ответы хороши, но я думаю, что нашел замечательный метод, чтобы найти корни по модулю любого числа: этот метод основан на «LATTICES». Пусть г ≤ R быть корнем мод р. Мы должны найти другую функцию, такие, как Н (х) таким образом, что ч невелики и г является корнем ч. Метод решетки найдет эту функцию.В первый раз мы должны создать основу полинома для решетки, а затем с помощью алгоритма «LLL» находим «самый короткий вектор» с корнем r без модуля p. Фактически, мы удаляем по модулю p.

Подробнее см. «Coppersmith D. Найти небольшие решения для полиномов малой степени. В криптографии и решетках».