user13676

C ++: библиотека, которая находит корни полинома


C ++ Математический Софт

У меня есть вектор, v , коэффициента многочлена. Мне нужна библиотека с открытым исходным кодом, которая может быть использована в C ++ и находит корни полинома mod N.

Поэтому я могу дать ему v и модуль N , и он возвращает корни. Заметим, что коэффициенты были вычислены путем интерполяции некоторых пар (x_i, y_i) .

Он должен поддерживать большое целое число.

Shokatsuryō
Привет, @ user13676. Я хочу спросить, N - простое число? Я думаю, что ваша проблема является частью алгоритма криптографии. Понятия не имею.

Ответы


Tomasz Klim

Вы не найдете ничего, что одновременно работает на больших количествах и делает такие расчеты.

Здесь у вас есть рабочий код, который работает с «нормальными» номерами:

http://www.codeproject.com/Articles/674149/A-Real-Polynomial-Class-with-Root-Finder

Вы можете переопределить алгоритм, используя, например. Библиотека GNU MP (у нее есть полные C ++ привязки и множество примеров в Интернете).

user13676
Чтобы сообщить читателям, что мне удалось использовать библиотеку NTL для интерполяции и извлечения корней. Для интерполяции я сделал небольшую модификацию в библиотеке. Для извлечения корня я использовал факторизацию, а затем алгоритм поиска корней. Интерполяция была довольно быстрой, но извлечение корня (и факторизация), когда степень полинома больше 1000, становится медленной, однако она выполняет эту работу. Наконец, он поддерживает большое целое число.

Смотри также