5

如果 F := GF(p^n) 是具有 p^n 个元素的有限域，其中 p 是质数和 na 自然数，是否有任何有效的算法来计算 F 中两个元素的乘积？

到目前为止，这是我的想法：

我知道 F 的标准构造是在 GF(p) 中取 n 次不可约多项式 f，然后将 F 的元素视为商 GF(p)[X]/(f) 中的多项式，我有一个感觉这可能已经是正确的方法，因为多项式乘法和加法应该很容易实现，但我不知何故看不到这实际上是如何完成的。例如，如何选择合适的 f，以及如何获得任意多项式的等价类？

4

5 回答 5

5

首先在 GF[p] 上选择一个 n 次不可约多项式。只需生成随机多项式，随机多项式是不可约的，概率为 ~1/n。

要测试您的随机多项式，您需要一些代码来对 GF[p] 上的多项式进行因式分解，请参阅维基百科页面了解一些算法。

那么您在 GF[p^n] 中的元素只是 GF[p] 上的 n 次多项式。只需进行正常多项式算术，并确保以您的不可约多项式为模计算余数。

编写此方案的简单版本非常容易。在如何实现模运算方面，您可能会变得任意复杂。请参阅模幂运算、蒙哥马利乘法和使用 FFT 的乘法。

于 2010-01-03T02:09:15.720 回答
3

GF(p^n) 中的元素相乘是否有有效的算法取决于您如何表示 GF(p^n) 的元素。

正如你所说，一种方法确实是在 GF(p)(X)/(f) 中工作。加法和乘法在这里相对简单。然而，确定一个合适的不可约多项式 f 并不容易——据我所知，没有一种有效的算法来计算一个合适的 f。

另一种方法是使用所谓的Zech 对数。 Magma使用它们的预计算表来处理小的有限域。GAP也有可能这样做，尽管它的文档不太清楚。

使用数学结构进行计算通常非常棘手。您当然不会在这里遗漏任何明显的东西。

于 2009-12-20T15:01:50.513 回答
3

这取决于您的需求和您的领域。

当你乘法时，你必须选择 F x的生成器。当您添加时，您必须使用 F 是一些较小 F p m上的向量空间这一事实。在实践中，你经常做的是一些混合方法。例如，如果您在 F 256上工作，则采用 F 256 x的生成器 X ，并让 G 成为 F 16上的最小多项式。你现在有

(sum i 小于 16 a i X i )(sum j 小于 16 b j X j )= sum_k sum i+j = k a i b j X i+j

为了使乘法高效，您所要做的就是存储 F 16的乘法表，并（使用 G）根据 X 的较低幂和 F 16中的元素构造 X^m

最后，在 p n = 2 2 n的极少数情况下，您会得到 Conways 的 nimbers 场（请参阅 Conways “获胜方式”，或 Knuth 的第 4A 卷第 7.1.3 节），其中有非常有效的算法。

于 2009-12-21T10:35:35.387 回答
2

伽罗瓦域算术库（C++，mod 2，看起来不支持其他素数元素）

灵盒(C++)

MPFQ (C++)

但是，我对这些没有个人经验（我已经为 31 度或以下的伽罗瓦领域制作了自己的原始 C++ 类，没有什么太奇特或值得复制的东西）。就像提到的其中一位评论者一样，您可以查看mathoverflow.net——只要问得好，并确保您首先完成了作业。那里的人应该知道什么样的数学软件适合处理有限域，并且它与 mathoverflow 的兴趣领域足够接近，以至于一个陈述良好的问题不应该被关闭。

于 2009-12-20T15:34:21.263 回答
1

假设这是在有限域中执行乘法的算法的问题，当确定了一个不可约多项式 f(X) 时（否则考虑Rabin 的不可约性检验）

你有两个 n-1 次多项式

A(X) = a_0 + a_1*X + a_2*X^2 + ... + a_(n-1)*X^(n-1) and
B(X) = b_0 + b_1*X + b_2*X^2 + ... + b_(n-1)*X^(n-1)

系数a_k, b_k不在Z/pZ的代表{0,1,...,p-1}中。

产品定义为

C(X) = A(X)*B(X) % f(X),

其中模运算符 "%" 是多项式除法A(X)*B(X) / f(X)的余数。

以下是复杂度为 O(n^2) 的方法

1.) 根据分配律，产品可以分解为

  B(X) * X^(n-1) * a_(n-1)
+ B(X) * X^(n-2) * a_(n-2)
+ ...
+ B(X) * a_0

=

  (...(a_(n-1) * B(X)  * X 
   +  a_(n-2)  * B(X)) * X
   +  a_(n-3)  * B(X)) * X
   ...
   +  a_1      * B(X)) * X
   +  a_0      * B(X)

2.) 对于 %-运算符是从 Z/pZ[X] 到 GF(p^n) 的环同态，它可以应用于上述迭代的每个步骤。

 A(X)*B(X) % f(X) =

  (...(a_(n-1) * B(X)  * X % f(X)
   +  a_(n-2)  * B(X)) * X % f(X)
   +  a_(n-3)  * B(X)) * X % f(X)
   ...
   +  a_1      * B(X)) * X % f(X)
   +  a_0      * B(X)

3.) 每次与X相乘后，即系数空间的移位，您将得到一个n次多项式T_k(X)，元素为 t_kn * X^n。减少模f(X)由

T_k(X) % f(X) = T_k(X) - t_kn*f(X),

这是一个 n-1 次的多项式。

最后，用归约多项式

r(x) := f(x) - X^n  and

T_k(X) =: t_kn * X^n + U_(n-1)(X)

T_k(X) % f(X) = t_kn * X^n + U_(n-1)(X) - t_kn*( r(x) + X^n)
              = U_(n-1)(X) - t_kn*r(x)

即，所有步骤都可以用最大 n-1 次的多项式来完成。

于 2021-03-27T01:19:16.397 回答