How to get Coefficients of polynomial of degree n mod p?

Question

F(x) = a₀ + a₁x + a₂x² + . . . + a_nxⁿ is a polynomial function of degree n, there are sufficient methods for finding the coefficients of polynomial equation F(x). (i.e. finding values of a₀ , a₁, a₂, . . . a_n)

However, I was wondering on how to get coefficients of equation F(x) = (a₀ + a₁x + a₂x² + . . . + a_nxⁿ) % p. Where p is a prime number.

For example, consider the equation
 F(x) = (a₀ + a₁x + a₂x²) % p
 Let a₀ = 5, a₁ = 3 and a₃ = 2,
 and P = 71 then F(10) = 22, F(20) = 13, F(30) = 49 for x = 10, 20, 30.

Is there any way to find the same coefficients of F(x) (i.e. a₀, a₁ and a₂) from the data P(=71) ,F(10), F(20), F(30) for x = 10, 20, 30 ?

Answer 1

You can solve it as a set of linear equations. For addition subtraction and multiplication, perform operations modulo n. For dividing, multiply with the multiplicative inverse. Take the example given in the question. The equations become:

(All calculated on mod 71)

1. a0 + 10a1 + 29a2 == 22 
2. a0 + 20a1 + 45a2 == 13 
3. a0 + 30a1 + 48a2 == 49

Subtract equations 1 from 2

4. 10a1 + 16a2 == 62    

Subtract equations 2 from 3

5. 10a1 + 3a2 == 36 

Subtract 5 from 4 to get

13a2 == 26
=>a2 == 26/13 == 26*11 == 2

The same methods that are applied to general polynomials can be modified. For instance, we can use a matrix to solve the set of linear equations programmatically.