Целочисленные корни многочлена

10

Какой алгоритм мы можем использовать, чтобы найти все целочисленные корни многочлена с целыми коэффициентами?f(x)

Я замечаю, что Мудрец может найти корни в течение нескольких секунд, даже когда все коэффициенты очень велики. Как это может сделать это?f(x)

ds.algorithms na.numerical-analysis user12290
источник
1
Вы ищете алгоритм для возврата целочисленного корня заданного полинома? Если да, то это неразрешимо, и вопрос здесь не по теме. Вы можете спросить об этом в области компьютерных наук, которая имеет более широкий охват.
Каве
7
Оставайтесь на линии. Почему неразрешимость делает вопрос не по теме? Это законный вопрос исследовательского уровня.
Джефф
2
Итак, как же Sage это делает? Быть неразрешимым - даже если известно, что оно неразрешимо - не делает проблему теоретически неинтересной. Теоретические компьютерные ученые все время решают неразрешимые проблемы - например, см. Все компьютерные проверки.
Джефф
11
Kaveh, то, что вы говорите, не соответствует действительности. Что неразрешимо, так это разрешимость диофантовых уравнений со многими переменными (так что реальных решений легко бесконечно много, и каждый ищет целочисленное / рациональное решение). Но этот вопрос касается многовариантного многочлена , который, конечно, разрешим (если имеет степень , существует до корней, и можно проверить, какое из них является целым числом). f(x)f(x)dd
Махди Черагчи
1
@Pratik Вам не нужны базы Гребнера в одномерном случае.
Юваль Фильмус

Ответы:

10

Предполагая, что коэффициенты являются целыми или рациональными и что вам нужны целочисленные корни, самый простой подход состоит в использовании целочисленной или рациональной теоремы о корне. См. Http://en.wikipedia.org/wiki/Rational_root_theorem. Как отмечает DW, это может быть проблематично, если постоянный коэффициент трудно учитывать (см. Также /math/123018/polynomial- и-целочисленные корни )f

В любом случае документация Sage четко объясняет, как они выполняют поиск в корне: «Следующий метод, который используется, если K является целочисленной областью, состоит в том, чтобы попытаться разложить многочлен. Если это удастся, то для каждой степени один фактор a * x + b, мы добавляем -b / a в качестве корня (пока этот фактор действительно находится в нужном кольце). " См. Http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html .

Итак, ваш вопрос звучит так: как они эффективно разлагают многочлены с целыми коэффициентами? Очевидно, Sage вызывает NTL для этого ( подробности NTL см. В http://www.shoup.net/ntl/doc/ZZXFactoring.txt ).

Если вам нужен асимптотически эффективный метод, вы можете обратиться к методу Lenstra, Lenstra и Lovasz ( https://openaccess.leidenuniv.nl/handle/1887/3810 ).

Минар
источник
1
Спасибо за полезный совет! Захватывающий. Можете ли вы отредактировать свой ответ, чтобы уточнить, как превратить его в алгоритм, и каково его время выполнения? Является ли время выполнения в наихудшем случае экспоненциальным (потому что может потребоваться субэкспоненциальное время для вычисления фактора, и тогда может быть экспоненциально много делителей ведущего и конечного коэффициентов)? Если да, то есть ли лучшие алгоритмы или это лучшее, что можно сделать? Кроме того, разве этот подход не находит только рациональные корни, но не иррациональные корни?
DW
Перечитывая вопрос и видя, что вы толкуете его по-разному, я больше не полностью уверен, но мне и некоторым авторам стало ясно, что вопрос задается о целочисленных корнях. Разве вы не читаете это так?
минар
@minar, ты прав. Теперь, когда я перечитал вопрос, он кажется таким. Должно быть, я прочитал вопрос слишком быстро. (Первоначально я неверно истолковал вопрос как подразумевающий, что мы хотим, чтобы все корни многочлена имели целочисленные коэффициенты, но при перечитывании вопроса это выглядит как неправильное толкование.)
DW
2
Для асимптотически и практически эффективного метода наиболее известным алгоритмом является Ван Хой (см. Здесь ). На самом деле NTL, похоже, использует его.
Бруно