计算几个方程

Question

具有以下职能：

f(x)= 4(x-1)(x-3)/(0-1)(0-3)
g(x)= 2(x-0)(x-3)/(1-0)(1-3)
h(x)= 3(x-0)(x-1)/(3-0)(3-1)

我想计算一下他们的和mod p。供参考，p=7。

然而，我最感兴趣的是最后结果中x的幂系数。会让你明白我的意思

我的脚步：

f(x)=4(x-1)(x-3)/3
g(x)=-(x-0)(x-3)
h(x)=(x-0)(x-1)/2

f(x)+g(x)+h(x)=(8(x-1)(x-3)-6(x-0)(x-3)+3(x-0)(x-1))/6
=(8(x^2-4x+3)-6(x^2-3x)+3(x^2-x))/6
=(8x^2-32x+24-6x^2+18x+3x^2-3x)/6
=(5x^2-17x+24)/6

1/6 mod 7=6

因此，我们可以用6乘以，而不是除以括号，这也将成为mod 7：

=(5x^2-17x+24)*6
=30x^2-102+144 

这也将是mod 7，但如果我可以得到系数，我可以分别为他们每一个。最终结果将是2x^2+3x+4

所以，我感兴趣的是系数30，-102和144(或者2,3,4，不重要)。如果有一种更快或更简单的方法(我可能在计算中做了一些无用的步骤)，那么如何用java进行计算才能从f+g+h中得到它们呢？

Answer 1

据我所见，您正在计算Lagrange多项式。

在3个数据点(x_0，y_0)，(x_1，y_1)，(x_2，y_2)的具体情况下--在您的示例中它们是(0，4)，(1，2)，(3，3)，计算非常容易。

f(x) = y_*l_0(x) =y_0/((x_0-x_1)*(x_0-x_2)*(x^2+ -(x_1+x_2)*x + (x_1*x_2))

另外两个多项式也可以类似地计算。

在它们的求和中，您只需将相应的系数组合在一起，并做出模算法。(利用逆元的乘法可以进行除法，在素数为a^(p-2)的情况下，利用费马小定理可以方便地计算逆元。)