Ask Your Question

Lagrange interpolation over a finite field

asked 2017-11-22 20:13:14 +0200

this post is marked as community wiki

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2017-11-23 17:20:52 +0200

B r u n o gravatar image

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.

edit flag offensive delete link more


hi, does sage have newton interpolation method ?

abraham gravatar imageabraham ( 2021-11-19 15:02:57 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2017-11-22 20:13:14 +0200

Seen: 5,495 times

Last updated: Nov 23 '17