galois.Poly.roots(multiplicity: False = False) → Array
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.

Notes

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 [1]: f = galois.Poly.Roots([1, 0], multiplicities=[7, 3]); f
Out[1]: Poly(x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3, GF(2))

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

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

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

In [4]: GF = galois.GF(3**5)

In [5]: f = galois.Poly.Roots([18, 227, 153], multiplicities=[5, 7, 3], field=GF); f
Out[5]: 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 [6]: f.roots()
Out[6]: GF([ 18, 153, 227], order=3^5)

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