0

有这些功能：

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 中获取它们？

4

1 回答 1

1

据我所知，您正在计算Lagrange polynomials。

在 3 个数据点 (x_0, y_0), (x_1, y_1), (x_2, y_2) 的特定情况下 - 在您的示例中是 (0, 4), (1, 2), (3, 3)，计算很容易。

f(x) = y_0*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)。）

于 2014-03-22T10:11:18.883 回答