Фактор многочлен над конечным полем или целыми числами

20

Без использования каких-либо встроенных функций факторинга / полинома разложите полином полностью на неприводимые числа или целое конечное поле.

вход

Ваша программа / функция получит некоторое простое (или нулевое) число в nкачестве входных данных. Поле / кольцо является конечным полем этого порядка (то есть Z/nZ), или просто Zесли nесть 0. Ваша программа может потерпеть неудачу, если nнет 0или простое число. Полином будет в F[x].

Ваша программа / функция также получит многочлен в качестве входных данных.

Существует некоторая гибкость во вводе, обязательно укажите, как вы собираетесь получать ввод. Например, полином может быть введен в виде списка коэффициентов или в форме, которую большинство людей ожидают (например:) 50x^3 + x^2, или в какой-то другой разумной форме. Или формат ввода поля / кольца также может быть другим.

Выход

Ваша программа / функция выведет полиномиальное множитель полностью. Вы можете оставить несколько корней расширенными (т.е. (x + 1)(x + 1)вместо (x + 1)^2). Вы можете удалить пробел между двоичными операторами. Вы можете заменить сопоставление с *. Вы можете вставить пробел в странные места. Вы можете изменить порядок факторов в любом порядке. xТермин может быть просто (x). xможно записать как x^1; Однако постоянный член может не иметь x^0. Посторонние +признаки допустимы. Вы не можете иметь термин с 0перед, они должны быть пропущены. Ведущий член каждого фактора должен быть положительным, отрицательные признаки должны быть снаружи.

Тестовые случаи, ваша программа должна иметь возможность производить вывод для каждого из них в разумные сроки (скажем, <= 2 часа):

Входные данные: 2, x^3 + x^2 + x + 1

Выход: (x + 1)^3

Входные данные: 0, x^3 + x^2 + x + 1

Выход: (x + 1)(x^2 + 1)

Входные данные: 0, 6x^4 – 11x^3 + 8x^2 – 33x – 30

Выход: (3x + 2)(2x - 5)(x^2 + 3)

Входные данные: 5, x^4 + 4x^3 + 4x^2 + x

Выход: x(x + 4)(x + 4)(x + 1)

Входные данные: 0, x^5 + 5x^3 + x^2 + 4x + 1

Выход: (x^3 + 4x + 1)(x^2 + 1)

Отдельное спасибо Питеру Тейлору за критику моих тестов

Джастин
источник
1
Я думаю, что это дает мне воспоминание о некоторых из сложнейших курсов по математике . Я даже иду в правильном направлении здесь?
Цифровая травма
1
Это напоминает мне о том времени, когда мне снились кошмары, когда я пытался правильно напечатать многочлены ...
Sp3000
Извините, что я не понял, но что должен делать первый номер ввода? или как это влияет на вывод?
Оптимизатор
@Optimizer Первый входной номер определяет, над каким полем / целыми числами вы работаете. Если число ненулевое, вы работаете над конечным полем этого порядка. Конечное поле порядка pимеет элементы, {0, 1, ... , p-1}и оно находится в режиме сложения / умножения p. В принципе, уменьшите любой коэффициент по моду, pи все хорошо. Кроме того, обратите внимание, что если у него есть корень, то есть линейный коэффициент, один из {0, ... , p-1}будет производить 0(мод p), когда он подключен к полиному.
Джастин
1
@flawr, стандартный подход к факторингу Zзаключается в подборе Z/pZподходящего, pа затем гензелевого лифта. Тем не менее, подход к игре в гольф, вероятно, (и это, конечно, маршрут, который я смотрю), чтобы использовать простую оценку высоты факторов и грубую силу.
Питер Тейлор

Ответы:

17

GolfScript (222 байта)

~.@:q@.0\{abs+}/2@,2/)?*or:^{\1$^base{^q- 2/-}%.0=1=1$0=q>+{{:D[1$.,2$,-)0:e;{.0=0D=%e|:e;(D(@\/:x@@[{x*~)}%\]zip{{+}*q!!{q%}*}%}*e+])0-{;0}{@;@\D.}if}do}*;\).^3$,)2/?<}do;][[1]]-{'('\.,:x;{.`'+'\+'x^'x(:x+x!!*+\!!*}%')'}/

Онлайн демо

Примечания

  1. За входным форматом nследует массив коэффициентов GolfScript от самых младших к значимым. Например, 0, x^5 + 5x^3 + x^2 + 4x + 1должен быть отформатирован как 0 [1 0 5 1 4 1].
  2. Над конечным полем существует только конечное число многочленов достаточно малой степени, чтобы быть релевантными. Однако это еще не конец Z. Я справляюсь Z, используя расслабленную форму ограничения высоты Миньоты. Отличная статья о границах роста в факторинге - « Границы факторов в Z» [x] , Джон Эбботт, 2009 (ссылка на препринт arxiv; его резюме говорит, что оно было принято Журналом символических вычислений ). Самая расслабленная форма, приведенная здесь, относится к норме L-2, но чтобы сохранить байты, я расслабляюсь дальше и вместо этого использую норму L-1. Тогда это случай грубого принуждения путем пробного деления.
  3. Над конечным полем каждый многочлен является константой, умноженной на монический многочлен, поэтому я делаю только пробное деление на монические многочлены и сохраняю обратную величину в поле. Тем не менее, Zэто всего лишь кольцо, и поэтому необходимо провести пробное деление по немоническим факторам-кандидатам. Мне удается обойтись без реализации рациональных чисел, выполнив тест с делением лидирующих факторов и накапливая флаг «ошибки» e.
  4. Обе точки 2 и 3 подразумевают, что случай факторинга, Zкак правило, медленнее и не может быть протестирован с онлайн-демонстрацией. Однако самый медленный из официальных тестовых случаев занимает 10 минут, что находится в пределах «разумного» срока.
Питер Тейлор
источник