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

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

Эта страница существует благодаря следующим персонам

Anton

Создан: 2019-09-08 06:53:07, Последнее изменение: 2020-11-03 14:19:37
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/8332/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).

Этот калькулятор находит все неразлагаемые множители многочлена одной переменной по модулю 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 Факторизация полиномов 

Ссылка скопирована в буфер обмена
PLANETCALC, Разложение многочлена на множители по модулю

Комментарии