galois.Poly.roots(multiplicity: False = False)
galois.Poly.roots(multiplicity: True) tuple[Array, np.ndarray]

Calculates the roots $$r$$ of the polynomial $$f(x)$$, such that $$f(r) = 0$$.

Parameters:
multiplicity: False = False
multiplicity: True

Optionally return the multiplicity of each root. The default is False which only returns the unique roots.

Returns:

• An array of roots of $$f(x)$$. The roots are ordered in increasing order.

• The multiplicity of each root. This is only returned if multiplicity=True.

This implementation uses Chien’s search to find the roots $$\{r_1, r_2, \dots, r_k\}$$ of the degree-$$d$$ polynomial

$f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0,$

where $$k \le d$$. Then, $$f(x)$$ can be factored as

$f(x) = (x - r_1)^{m_1} (x - r_2)^{m_2} \dots (x - r_k)^{m_k},$

where $$m_i$$ is the multiplicity of root $$r_i$$ and $$d = \sum_{i=1}^{k} m_i$$.

The Galois field elements can be represented as $$\mathrm{GF}(p^m) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{p^m-2}\}$$, where $$\alpha$$ is a primitive element of $$\mathrm{GF}(p^m)$$.

0 is a root of $$f(x)$$ if $$a_0 = 0$$. 1 is a root of $$f(x)$$ if $$\sum_{j=0}^{d} a_j = 0$$. The remaining elements of $$\mathrm{GF}(p^m)$$ are powers of $$\alpha$$. The following equations calculate $$f(\alpha^i)$$, where $$\alpha^i$$ is a root of $$f(x)$$ if $$f(\alpha^i) = 0$$.

$\begin{split} f(\alpha^i) &= a_{d}(\alpha^i)^{d} + \dots + a_1(\alpha^i) + a_0 \\ &\overset{\Delta}{=} \lambda_{i,d} + \dots + \lambda_{i,1} + \lambda_{i,0} \\ &= \sum_{j=0}^{d} \lambda_{i,j} \end{split}$

The next power of $$\alpha$$ can be easily calculated from the previous calculation.

$\begin{split} f(\alpha^{i+1}) &= a_{d}(\alpha^{i+1})^{d} + \dots + a_1(\alpha^{i+1}) + a_0 \\ &= a_{d}(\alpha^i)^{d}\alpha^d + \dots + a_1(\alpha^i)\alpha + a_0 \\ &= \lambda_{i,d}\alpha^d + \dots + \lambda_{i,1}\alpha + \lambda_{i,0} \\ &= \sum_{j=0}^{d} \lambda_{i,j}\alpha^j \end{split}$

Examples

Find the roots of a polynomial over $$\mathrm{GF}(2)$$.

In : f = galois.Poly.Roots([1, 0], multiplicities=[7, 3]); f
Out: Poly(x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3, GF(2))

In : f.roots()
Out: GF([0, 1], order=2)

In : f.roots(multiplicity=True)
Out: (GF([0, 1], order=2), array([3, 7]))


Find the roots of a polynomial over $$\mathrm{GF}(3^5)$$.

In : GF = galois.GF(3**5)

In : f = galois.Poly.Roots([18, 227, 153], multiplicities=[5, 7, 3], field=GF); f
Out: Poly(x^15 + 118x^14 + 172x^13 + 50x^12 + 204x^11 + 202x^10 + 141x^9 + 153x^8 + 107x^7 + 187x^6 + 66x^5 + 221x^4 + 114x^3 + 121x^2 + 226x + 13, GF(3^5))

In : f.roots()
Out: GF([ 18, 153, 227], order=3^5)

In : f.roots(multiplicity=True)
Out: (GF([ 18, 153, 227], order=3^5), array([5, 3, 7]))