Univariate Lagrange Interpolation Over Finite Field

Answer

f(x)=13x4+9x3+3x2+8x+3f(x) = 13x^{4} + 9x^{3} + 3x^{2} + 8x + 3

Evaluation

f(f())=7= 7

Step by Step Solution

General Form

f(x)=y0L0+y1L1+y2L2+...+yn−1Ln−1f(x) = y_0L_0 + y_1L_1 + y_2L_2 + ... + y_{n-1}L_{n-1}Li=∏j=0,j≠in−1(x−xjxi−xj)L_i = \prod_{j=0, j \neq i}^{n - 1}(\dfrac{x-x_j}{x_i-x_j})

Finding the Lagrange Polynomials

L0=(x−x1x0−x1)(x−x2x0−x2)(x−x3x0−x3)(x−x4x0−x4)L_0 = (\dfrac{x - x_1}{x_0 - x_1})(\dfrac{x - x_2}{x_0 - x_2})(\dfrac{x - x_3}{x_0 - x_3})(\dfrac{x - x_4}{x_0 - x_4})
=(x−10−1)(x−20−2)(x−30−3)(x−40−4)= (\dfrac{x - 1}{0 - 1})(\dfrac{x - 2}{0 - 2})(\dfrac{x - 3}{0 - 3})(\dfrac{x - 4}{0 - 4})
=5(x−1)(x−2)(x−3)(x−4)= 5(x - 1)(x - 2)(x - 3)(x - 4)
L0=5x4+1x3+5x2+5x+1L_0 = 5x^4 + 1x^3 + 5x^2 + 5x + 1
L1=(x−x0x1−x0)(x−x2x1−x2)(x−x3x1−x3)(x−x4x1−x4)L_1 = (\dfrac{x - x_0}{x_1 - x_0})(\dfrac{x - x_2}{x_1 - x_2})(\dfrac{x - x_3}{x_1 - x_3})(\dfrac{x - x_4}{x_1 - x_4})
=(x−01−0)(x−21−2)(x−31−3)(x−41−4)= (\dfrac{x - 0}{1 - 0})(\dfrac{x - 2}{1 - 2})(\dfrac{x - 3}{1 - 3})(\dfrac{x - 4}{1 - 4})
=14(x−0)(x−2)(x−3)(x−4)= 14(x - 0)(x - 2)(x - 3)(x - 4)
L1=14x4+10x3+7x2+4xL_1 = 14x^4 + 10x^3 + 7x^2 + 4x
L2=(x−x0x2−x0)(x−x1x2−x1)(x−x3x2−x3)(x−x4x2−x4)L_2 = (\dfrac{x - x_0}{x_2 - x_0})(\dfrac{x - x_1}{x_2 - x_1})(\dfrac{x - x_3}{x_2 - x_3})(\dfrac{x - x_4}{x_2 - x_4})
=(x−02−0)(x−12−1)(x−32−3)(x−42−4)= (\dfrac{x - 0}{2 - 0})(\dfrac{x - 1}{2 - 1})(\dfrac{x - 3}{2 - 3})(\dfrac{x - 4}{2 - 4})
=13(x−0)(x−1)(x−3)(x−4)= 13(x - 0)(x - 1)(x - 3)(x - 4)
L2=13x4+15x3+9x2+14xL_2 = 13x^4 + 15x^3 + 9x^2 + 14x
L3=(x−x0x3−x0)(x−x1x3−x1)(x−x2x3−x2)(x−x4x3−x4)L_3 = (\dfrac{x - x_0}{x_3 - x_0})(\dfrac{x - x_1}{x_3 - x_1})(\dfrac{x - x_2}{x_3 - x_2})(\dfrac{x - x_4}{x_3 - x_4})
=(x−03−0)(x−13−1)(x−23−2)(x−43−4)= (\dfrac{x - 0}{3 - 0})(\dfrac{x - 1}{3 - 1})(\dfrac{x - 2}{3 - 2})(\dfrac{x - 4}{3 - 4})
=14(x−0)(x−1)(x−2)(x−4)= 14(x - 0)(x - 1)(x - 2)(x - 4)
L3=14x4+4x3+9x2+7xL_3 = 14x^4 + 4x^3 + 9x^2 + 7x
L4=(x−x0x4−x0)(x−x1x4−x1)(x−x2x4−x2)(x−x3x4−x3)L_4 = (\dfrac{x - x_0}{x_4 - x_0})(\dfrac{x - x_1}{x_4 - x_1})(\dfrac{x - x_2}{x_4 - x_2})(\dfrac{x - x_3}{x_4 - x_3})
=(x−04−0)(x−14−1)(x−24−2)(x−34−3)= (\dfrac{x - 0}{4 - 0})(\dfrac{x - 1}{4 - 1})(\dfrac{x - 2}{4 - 2})(\dfrac{x - 3}{4 - 3})
=5(x−0)(x−1)(x−2)(x−3)= 5(x - 0)(x - 1)(x - 2)(x - 3)
L4=5x4+4x3+4x2+4xL_4 = 5x^4 + 4x^3 + 4x^2 + 4x

Get the Final Polynomial

f(x)=3(5x4+1x3+5x2+5x+1)+2(14x4+10x3+7x2+4x)+5(13x4+15x3+9x2+14x)+7(14x4+4x3+9x2+7x)+9(5x4+4x3+4x2+4x)f(x) = 3( 5x^4 + 1x^3 + 5x^2 + 5x + 1) +2( 14x^4 + 10x^3 + 7x^2 + 4x ) +5( 13x^4 + 15x^3 + 9x^2 + 14x ) +7( 14x^4 + 4x^3 + 9x^2 + 7x ) +9( 5x^4 + 4x^3 + 4x^2 + 4x )
f(x)=13x4+9x3+3x2+8x+3f(x) = 13x^4 + 9x^3 + 3x^2 + 8x + 3