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

In [1]: GF = galois.GF(2**4)

In [2]: x = GF.Elements(); x
Out[2]: 
GF([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15],
   order=2^4)

In [3]: y = GF.Random(GF.order); y
Out[3]: 
GF([ 6,  7,  7,  9, 13,  0, 15, 15,  0, 10,  8, 15, 14, 11, 12,  2],
   order=2^4)

In [4]: L = galois.lagrange_poly(x, y); L
Out[4]: Poly(4x^15 + 13x^14 + 6x^13 + 8x^12 + 13x^11 + x^10 + 11x^9 + 4x^8 + 13x^6 + 7x^4 + 11x^3 + 12x^2 + 8x + 6, GF(2^4))

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