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


Show that the polynomial evaluated at $$x$$ is $$y$$.

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