galois.lagrange_poly¶

galois.lagrange_poly(x, y)¶

Computes the Lagrange interpolating polynomial \(L(x)\) such that \(L(x_i) = y_i\).

Parameters¶

x : FieldArray¶

An array of \(x_i\) values for the coordinates \((x_i, y_i)\). Must be 1-D. Must have no duplicate entries.

y : FieldArray¶

An array of \(y_i\) values for the coordinates \((x_i, y_i)\). Must be 1-D. Must be the same size as \(x\).

Returns¶

The Lagrange polynomial \(L(x)\).

Return type¶

Poly

Notes

The Lagrange interpolating polynomial is defined as

\[ \begin{align}\begin{aligned}L(x) = \sum_{j=0}^{k-1} y_j \ell_j(x)\\\begin{split}\ell_j(x) = \prod_{\substack{0 \le m < k \\ m \ne j}} \frac{x - x_m}{x_j - x_m} .\end{split}\end{aligned}\end{align} \]

It is the polynomial of minimal degree that satisfies \(L(x_i) = y_i\).

References

• https://en.wikipedia.org/wiki/Lagrange_polynomial

Examples

Create random \((x, y)\) pairs in \(\mathrm{GF}(3^2)\).

In [1]: GF = galois.GF(3**2)

In [2]: x = GF.Elements(); x
Out[2]: GF([0, 1, 2, 3, 4, 5, 6, 7, 8], order=3^2)

In [3]: y = GF.Random(x.size); y
Out[3]: GF([7, 1, 8, 6, 1, 7, 0, 8, 8], order=3^2)

Find the Lagrange polynomial that interpolates the coordinates.

In [4]: L = galois.lagrange_poly(x, y); L
Out[4]: Poly(2x^8 + x^7 + 5x^6 + 6x^5 + 6x^4 + 7x^3 + 7x^2 + 5x + 7, GF(3^2))

Show that the polynomial evaluated at \(x\) is \(y\).

In [5]: np.array_equal(L(x), y)
Out[5]: True