# Lagrange interpolation over a finite field

This post is a wiki. Anyone with karma >750 is welcome to improve it.

Sorry if this is obvious I am not a mathematician and am only trying to do this to learn about Samir's Secret Sharing scheme which uses a finite field for security.

I've read the Sage doc here on univariate polynomial rings which works fine. but now I am curious as to how this would be done over a finite field instead in sage?

Is it simply a matter of every point being taken mod some prime? Or would this not work.

edit retag close merge delete

Sort by » oldest newest most voted

I do not see what is your question. But just in case, the method lagrange_polynomial works for polynomials over finite fields as well. For instance with random chosen points:

sage: F = GF(17)
sage: points = [(F.random_element(), F.random_element()) for _ in range(3)]
sage: points # check that we don't have two evaluations for a same point!
[(15, 11), (5, 10), (8, 7)]
sage: R = F['x']
sage: R.lagrange_polynomial(points)
14*x^2 + 4*x + 14


If the question is about the algorithm to perform such a computation, note that the definition of the Lagrange polynomial perfectly works over finite fields, so that there is no special difficulty.

more