galois.lagrange_poly(x: Array, y: Array) → Poly

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

Parameters:
x: Array

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

y: Array

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)\).

Notes

The Lagrange interpolating polynomial is defined as

\[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}\]

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([8, 6, 3, 4, 7, 5, 4, 3, 3], 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^6 + 5x^5 + 3x^4 + 5x^3 + x^2 + 2x + 8, GF(3^2))

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

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