1

Let's say I have a polynomial of degree $n$ over a finite field. And I calculate n+1 points on this polynomial, say $(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n)$.

Now, can I use these points to get the coefficients of the polynomial using Vandermonde matrix?

My specific doubt would be, since the points were evaluated over a finite field, can we still use Vandermonde matrix? If so, how would we go about it?

I do know we can use Lagrange Interpolation and Finite Field arithmetic to get the coefficients, but is there a way to use finite field arithmetic with vandermonde matrix to retrieve the coefficients?

Michael Hardy
  • 1
crypt
  • 38
  • To obtain the coefficients of the polynomial, you will have to invert the Vandermonde matrix. My understanding is that calculating the Langrange polynomial is equivalent to inverting the Vandermode matrix. In either case there are no assumptions made about the field. – Oliver Clarke Apr 06 '20 at 21:54
  • @Ollie When we calculate using Lagrange Polynomial, we use FInite field arithmetic, if we know our polynomial defined over it. But I'm not sure how to take that into account when inverting Vandermonde Matrix. – crypt Apr 06 '20 at 21:58
  • If I understand the question correctly, you would like to know how to invert a matrix whose entries belong to a finite field. If so then one way it to calculate the inverse is to calculate the adjugate matrix and the determinant. The entries of the adjugate matrix are sums and products of entries of your original matrix. To perform those sums and products we will follow the operations of the finite field. Similarly for the determinant which is again sums and products of entries of the matrix. – Oliver Clarke Apr 06 '20 at 22:18
  • It's that simple,huh, That seems like a resaonable answer. If you can put it as an answer to the question, I'll mark it as solved. Thank you @Ollie. – crypt Apr 07 '20 at 12:05

1 Answers1

0

From the comments on the original post, it seems the question is asking how to calculate the inverse of the Vandermonde matrix whose entries lie in some finite field.

To invert this matrix, call it $A$, one can first calculate the adjugate matrix $Adj(A)$ whose entries are sums and products of entries from $A$ - to perform these operations we use the operations defined by the finite field. The adjugate matrix has the nice property that $Adj(A) \cdot A = \det(A) I$, where $I$ is the identity matrix. So to calculate $A^{-1} = (1/\det(A))Adj(A)$ it remains to find $\det(A)$. However the determinant can be calculated by taking sums and products of entries of $A$.

Oliver Clarke
  • 1,425