2

I have a vector, v, of coefficient of a polynomial. I need a (open source) library that can be used in C++ and finds the roots of polynomial mod N.

So I can give it v and modulus N, and it returns the roots. Note that the coefficients have been computed by interpolating some pairs (x_i , y_i).

It should support big integer.

2

You won't find anything that is both operates on big numbers and do such calculations.

Here you have a working code, that operates on "normal" numbers:

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

You can reimplement the algorithm using eg. GNU MP library (it has complete C++ bindings and lots of examples on the web).

  • Just to let the readers know that I managed to use NTL library for both interpolation and root extraction. For interpolation I made a minor modification to the library. For root extraction I used factorization and then root finding algorithm. The interpolation was pretty fast but root extraction (and factorization) when the degree of polynomial is greater than 1000 becomes slow, however it does the job. Finally it supports big integer too. – user13676 Jul 18 '15 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.