如何获得n度模p的多项式的系数？

Question

F(x) = a₀ + a₁x+a₂x² + . . . + a_nxⁿ 是n度的多项式函数，有足够的方法来寻找多项式方程F(x)的系数。(即求a的值₀ , a₁, a₂, . . . a_n然而，我想知道如何获得方程的系数。F(x) = (a₀ + a₁x+a₂x² + . . . + a_nxⁿ) % p. 其中p是一个质数。 例如，考虑公式F(x)=(a)₀ + a₁x+a₂x²) % p 让a₀ = 5, a₁ ＝3和a₃ ＝2，和 P = 71 然后 F(10) = 22, F(20) = 13, F(30) = 49 对于x=10，20，30。有什么办法可以找到 相同的F(x)系数。 (即a₀, a₁ 和a₂)的数据。P(=71) ,F(10), F(20), F(30) 对于x=10，20，30？

Answer 1

你可以把它作为一组线性方程来解。对于加减法和乘法，要进行模数n的运算，对于除法，要用乘法倒数乘法。以题中给出的例子为例．方程变为．

(都是根据模数71计算的)

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

从2中减去方程1

4. 10a1 + 16a2 == 62    

从3中减去方程2

5. 10a1 + 3a2 == 36 

从4中减去5，得到

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

应用于一般多项式的方法也可以进行修改。例如，我们可以使用矩阵来程序化地解决线性方程组。