如何在有限域中实现乘法?

首先选取GF[p]上n次不可约多项式。只要生成随机数,就可以得到一个随机多项式 irreducible with probability ~1/n

要测试随机多项式,需要一些代码来计算GF[p]上的多项式因子,请参阅 the wikipedia page

那么GF[p^n]中的元素就是GF[p]上的n次多项式。只需做普通多项式运算,并确保计算不可约多项式的余数模。

modular exponentiation , Montgomery multiplication ,并使用FFT进行乘法。

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

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

Zech's logarithms . Magma 用于处理小有限域的预计算表。有可能 GAP 做

用数学结构进行计算通常是相当棘手的。你肯定没有遗漏任何明显的东西。

这取决于你的需要和你的领域。

^x . 当你在加法的时候,你必须使用一个事实,即F是一个向量空间,在一些较小的F上 _^M . 实际上,你经常做的是一些混合的方法。例如,如果您正在为F工作 ,取一个F的发生器X ₂₅₆ 设G是F上的最小多项式 . 你现在有

(总和) _{我比16岁小 我} X ^我 )(总和) B _J X ^J )=sum_k sum _i+j=k A. B _J X ^i+j

₁₆

最后,在罕见的情况下 ^{2. N}

Galois Field Arithmetic Library

LinBox (C++)

MPFQ (C++)

我没有个人经验W/[这些],但是,(为GaloIS领域31度或更少的我自己的原始C++类,没有太异国情调或值得复制)。就像上面提到的一位评论者,你可以检查一下 mathoverflow.net

假设这是一个在有限域中执行乘法的问题,当一个不可约多项式f(x)被识别时(否则) Rabin's Test for Irreducibility

有两个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)

系数 没有代表了 {0,1,…,p-1} 属于 Z/pZ

产品定义为:

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

A(X)*B(X)/f(X) .

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

  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 ,即系数空间中的一个移位,你有一个多项式 图k(X) N 有元素 . 约化模 f(X) 由

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

最后,用约化多项式

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)

i、 e.所有步骤都可以使用最大次数n-1的多项式完成。