- galois.lagrange_poly(x: Array, y: Array) Poly
Computes the Lagrange interpolating polynomial \(L(x)\) such that \(L(x_i) = y_i\).
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, 0, 6, 3, 5, 8, 7, 2, 6], order=3^2)
Find the Lagrange polynomial that interpolates the coordinates.
In [4]: L = galois.lagrange_poly(x, y); L Out[4]: Poly(4x^7 + 7x^6 + 5x + 8, GF(3^2))
Show that the polynomial evaluated at \(x\) is \(y\).
In [5]: np.array_equal(L(x), y) Out[5]: True