Ask Your Question
0

Lagrange interpolation over a finite field

asked 2017-11-22 13:13:14 -0600

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
1

answered 2017-11-23 10:20:52 -0600

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

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

Stats

Asked: 2017-11-22 13:13:14 -0600

Seen: 34 times

Last updated: Nov 23