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.


1 Answer 1


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:


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
    Commented Jul 18, 2015 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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