2
$\begingroup$

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++.

$\endgroup$

marked as duplicate by nicoguaro, Kirill, Geoff Oxberry Jul 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.

  • $\begingroup$ 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? $\endgroup$ – Federico Poloni Jul 11 '15 at 17:45
  • $\begingroup$ @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. $\endgroup$ – user13676 Jul 11 '15 at 17:51
  • 1
    $\begingroup$ 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$. $\endgroup$ – Federico Poloni Jul 11 '15 at 18:21
  • 1
    $\begingroup$ So at which point do you need computations in $\mathbb{Z}_N$? $\endgroup$ – Federico Poloni Jul 11 '15 at 18:32
  • 1
    $\begingroup$ Cross-posted at mathoverflow.net/q/211307 , cstheory.stackexchange.com/q/31987 , and math.stackexchange.com/q/1357737 . $\endgroup$ – Emil Jeřábek supports Monica Jul 13 '15 at 13:23