Introduction to Cryptography with Coding Theory, 3rd Edition

D.8 Computations for Chapter 17

Lagrange interpolation

Suppose we want to find the polynomial of degree at most 3 that passes through the points $(1\text{,}1)\text{,}(2\text{,}2)\text{,}(3\text{,}21)\text{,}(5\text{,}12)$ mod the prime $p=37$. We first need to specify that we are working with polynomials in $x$ mod 37. Then we compute the polynomial:

R=PolynomialRing(GF(37),"x") 
f=R.lagrange_polynomial([(1,1),(2,2),(3,21), (5,12)]);f

This evaluates to

22*x^3 + 25*x^2 + 31*x + 34

If we want the constant term:

f(0) 
43