galois.lagrange_poly¶

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

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

Find the Lagrange polynomial that interpolates the coordinates.

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

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

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