# C++: How to find the roots of polynomial modulus N [duplicate]

This question already has an answer here:

I need to know what library, given a vector of coefficients and modulus N return the roots of polynomial modulus N. The library should support big integer. I'm coding in C++.

## marked as duplicate by nicoguaro♦, Kirill, Geoff OxberryJul 13 '15 at 20:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• What do you mean by "the roots of a polynomial modulus $N$"? The general definition, which you need if you want to find $d$ roots (with multiplicity) for every degree-$d$ polynomial, involves computing extensions of finite fields. These are only defined quite implicitly, up to isomorphisms and do not have a "canonical" presentation. Is this what you need? – Federico Poloni Jul 11 '15 at 17:45
• @FedericoPoloni Given $n$ pairs $(x_i, y_i)$ we can interpolate a polynomial or in fact the coefficients of polynomial. Let $x_i, y_i \in \mathbb{Z}_N$, and the same is true for the coefficients. Now Given these coefficients I need to find the roots of a polynomial mod N. Because the polynomial is indeed a polynomial ring. – user13676 Jul 11 '15 at 17:51
• What do you plan to do with these roots? A polynomial with coefficients in $\mathbb{Z}_N$ may have less roots than its degree, exactly like it happens in $\mathbb{R}$. For instance, $x^2+1$ in $\mathbb{Z}_7$. – Federico Poloni Jul 11 '15 at 18:21
• So at which point do you need computations in $\mathbb{Z}_N$? – Federico Poloni Jul 11 '15 at 18:32
• – Emil Jeřábek supports Monica Jul 13 '15 at 13:23