C++: Library that find the roots of polynomial

Question

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.

Hello, @user13676. I want to ask, is N a prime number? I think your problem is part of a cryptography algorithm. I have no idea. — meisyal, Jul 12, 2015 at 4:01
Cross-posted at scicomp.stackexchange.com/q/20143 , mathoverflow.net/q/211307 , math.stackexchange.com/q/1357737 , cstheory.stackexchange.com/q/31987 , and stackoverflow.com/q/31359678 . — Emil Jeřábek, Jul 13, 2015 at 13:28

Tomasz Klim · Accepted Answer · 2015-07-12 10:34:55Z

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:

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

answered Jul 12, 2015 at 10:34

Tomasz Klim

3914 silver badges10 bronze badges

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

Add a comment |

1 Answer 1