galois.lagrange_poly

galois.lagrange_poly(x, y)

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

Parameters
x : galois.FieldArray

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

y : galois.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

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

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([0, 1, 6, 6, 5, 5, 8, 7, 3], order=3^2)

Find the Lagrange polynomial that interpolates the coordinates.

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

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

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

Last update: Apr 03, 2022