homechevron_rightУчебаchevron_rightМатематикаchevron_rightАлгебра

Разложение многочлена на множители по модулю

Калькулятор находит неразлагаемые множители полинома в конечном поле

Этот калькулятор находит все неразлагаемые множители многочлена одной переменной по модулю p, используя алгоритм Элвина Берлекампа. Описание алгоритма следует за калькулятором.

PLANETCALC, Разложение многочлена на множители методом Берлекампа

Разложение многочлена на множители методом Берлекампа

Входной многочлен
 
Решение
 

Разложение многочлена на множители методом Берлекампа

Алгоритм представленный тут - это краткая компиляция алгоритма, описанного в Искусстве программирования Дональда Кнута 1.

Входные данные

  • u(x) - многочлен степени n, n>=2
  • p - модуль, простое число

Подготовка

  • Убедиться, что входной полином монический, если нет - разделить все коэффициенты на старший коэффициент un
  • Проверить, что полином свободен от квадратов используя Разложение многочлена в конечном поле свободное от квадратов
  • Для каждого свободного от квадратов множителя степени 2 и выше - прогнать следующий алгоритм

Алгоритм

  • Найти матрицу Q (n * n ), где n - степень многочлена по следующему алгоритму:
    • Инициализировать вектор A (a0, a1 ... an-1) = 1,0...0
    • Инициализировать первую строку матрицы Q (q0,0, q0,1 ... q0,n-1) = 0,0...0
    • Цикл по i = 1..n-1 выполнить:
      • Цикл по k = 1..n-1 выполнить:
        • Установить t = an-1
        • Цикл по j = n-1 .. 0 выполнить:
          • aj=aj-1-t*uj, подразумевается, что a-1 = 0
      • Установить значения строки i матрицы Q из вектора A
      • Вычесть 1 из элемента qi,i матрицы Q
  • Найти v[1] ... v[r] линейно независимые векторы, такие что v[1] Q = v[2] Q = ... v[r] Q = (0,0...0)
    • Установить все элементы n-размерного вектора C в -1 : c0 = c1 = .. = cn-1 = -1
    • Установить r = 0
    • Цикл по k = 0 ... n-1 выполнить:
      • Цикл по j = 0 ... n-1 выполнить:
        • Если qk,j ≠ 0 и cj<0
          • Установить a = qk,j
          • Умножить столбец j матрицы Q на -1/a
          • Добавить к оставшимся столбцам (i ≠ j) столбец j умноженный на qk,i
        • иначе (Если qk,j=0 или cj >= 0)
          • Установить r = r + 1
          • Установить каждый элемент i нового n-размерного вектора v[r] в одно из следующих значений:
            • ak,s, если найден такой s-элемент вектора C, такой, что cs = i
            • 1, если i = k
            • 0 - в противном случае
  • Найти r множителей полинома u(x), используя векторы v[2] ... v[r]
    • Найти все wi = gcd(u(x),v[2]-s) ≠ 1 для каждого s = 0 ... p
    • Если количество w < r выполнить:
    • Цикл по j=3 ... r до тех пор пока w < r
      • Заменить wi множителями, найденными алгоритмом Евклида: gcd(v[j]-s,wi) ≠ 1 для каждого s = 0 ... p


  1. Д.Кнут Искусство программирования том 2, пар. 4.6.2 Факторизация полиномов 

Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Разложение многочлена на множители по модулю

Комментарии