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

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

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

Коэффициенты полинома

Модуль

Рассчитать

Входной многочлен

 

Решение

 

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

 Ссылка  Сохранить  Виджет

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

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

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

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

Подготовка

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

Алгоритм

• Найти матрицу Q (n * n ), где n - степень многочлена по следующему алгоритму:
  • Инициализировать вектор A (a₀, a₁ ... a_n-1) = 1,0...0
  • Инициализировать первую строку матрицы Q (q_0,0, q_0,1 ... q_0,n-1) = 0,0...0
  • Цикл по i = 1..n-1 выполнить:
    • Цикл по k = 1..n-1 выполнить:
      • Установить t = a_n-1
      • Цикл по j = n-1 .. 0 выполнить:
        • a_j=a_j-1-t*u_j, подразумевается, что a_-1 = 0
    • Установить значения строки i матрицы Q из вектора A
    • Вычесть 1 из элемента q_i,i матрицы Q
• Найти v^[1] ... v^[r] линейно независимые векторы, такие что v^[1] Q = v^[2] Q = ... v^[r] Q = (0,0...0)
  • Установить все элементы n-размерного вектора C в -1 : c₀ = c₁ = .. = c_{n-1 = -1}
  • Установить r = 0
  • Цикл по k = 0 ... n-1 выполнить:
    • Цикл по j = 0 ... n-1 выполнить:
      • Если q_k,j ≠ 0 и c_j<0
        • Установить a = q_k,j
        • Умножить столбец j матрицы Q на -1/a
        • Добавить к оставшимся столбцам (i ≠ j) столбец j умноженный на q_k,i
      • иначе (Если q_k,j=0 или c_j >= 0)
        • Установить r = r + 1
        • Установить каждый элемент i нового n-размерного вектора v^[r] в одно из следующих значений:
          • a_k,s, если найден такой s-элемент вектора C, такой, что c_s = i
          • 1, если i = k
          • 0 - в противном случае
• Найти r множителей полинома u(x), используя векторы v^[2] ... v^[r]
  • Найти все w_i = gcd(u(x),v^[2]-s) ≠ 1 для каждого s = 0 ... p
  • Если количество w < r выполнить:
  • Цикл по j=3 ... r до тех пор пока w < r
    • Заменить w_i множителями, найденными алгоритмом Евклида: gcd(v^[j]-s,w_i) ≠ 1 для каждого s = 0 ... p