Корни многочлена по простому

Как показывает комментарий Макдовеллы, это довольно хорошо изучено. Вот как работает случайный алгоритм Кантора-Цассенхауса для случая, когда вы хотите найти корни полинома вместо более общей факторизации.

Обратите внимание, что в кольце многочленов с коэффициентами по модулю p произведение x (x-1) (x-2) ... (x-p + 1) имеет все возможные корни и равно x ^ px на Маленькая теорема Ферма и уникальная факторизация в этом кольце.

Установите g = GCD (f, x ^ p-x). Использование алгоритма Евклида для вычисления НОД двух многочленов, как правило, выполняется быстро и требует нескольких шагов, которые в максимальной степени являются логарифмическими. степень. Факторизация многочленов не требуется. g имеет те же корни, что и f в поле, и не имеет повторяющихся множителей.

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

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

Как часто это срабатывает? r_d имеет в качестве корней числа, которые на d меньше ненулевого квадрата по модулю 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).

Ваши ответы хороши, но я думаю, что нашел замечательный метод нахождения корней по модулю любого числа: этот метод, основанный на «РЕШЕТКАХ». Пусть r ≤ R будет корнем мода p. Мы должны найти другую функцию, такую ​​как h (x), такую, чтобы h не был большим, а r был корнем h . Решеточный метод найти эту функцию. Сначала мы должны создать базис полинома для решетки, а затем с помощью алгоритма «LLL» найти «кратчайший вектор», который имеет корень r без модуля p . Фактически, таким образом мы исключаем модуль p.