$ GF（p ^ n）= [f（0）\ bmod p，f（1）\ bmod p，\ dotsc， f（p ^ n-1）\ bmod p，f（p ^ n）\ bmod p] $
对于$ f（x）= \ sum_ {i = 0} ^ {n} \空间x ^ ik_i $，即具有常数$ K $的$ n $阶多项式。
我已经提到这些字段是双射的，因此对于输入集$ A $输出集$ B $包含与$ A $相同的值，但是顺序不同。
这是正确的吗？这有用于创建S盒的应用程序吗？
更新：
感谢您到目前为止的回答。我现在知道$ GF（p ^ n）$是一个大小为$ n $的向量数组，其每个元素都是根据多项式mod $ p $的结果计算的，但是我仍然不清楚它的。我最了解如何在这样的字段上执行矢量操作，但是对于如何使用这样的有限字段，我仍然不明智，更不用说将它们隐含在代码中了。我不太了解$ GF（p ^ n）$在构造上的样子，我想这正是我真正想要的。如果它是向量数组，且每个元素都是由某个多项式计算的，那么该多项式的输入如何确定？ $ GF $是一个函数，您可以向其中提供这样的值吗？输入值是整数，向量等吗？如果是这样，输入值是什么意思？向量在设定因子中的索引如何计算其值？
例如：
$ GF（p ^ n）[i] = \ begin {bmatrix} v_0 \\ v_1 \\ v_2 \\ ... \\ v_ {n-1} \ end {bmatrix} $
其中$ i $是该字段的索引，计算的矢量元素$ V $？提供什么输入？
#1 楼
$ GF（p ^ n）$中的$ GF $不是函数，它只是表示“ Galois域（$ p ^ n $个元素）”。关于Galois域是什么是的，它是一组有限的事物（例如，我们可以用从$ 0 $到$ p ^ n-1 $的数字表示），并在其上定义了一些数学运算（具体而言，加法和乘法及其反函数）我们将这些东西当作普通数字来进行计算，但是计算结果总是保留在有限集中。
具体来说，我们需要在此有限集中的元素上定义的运算为满足领域公理，其中包括您可能在中学代数课中学到的通常的关联性，可交换性和分布性规则。特别是，我们还要求每个元素$ a $都有一个加反的$ -a $和（如果$ a \ ne 0 $）有一个乘性逆$ 1 / a $，使得$ a +（-a）= 0和$ a \ times（1 / a）= 1 $。因此，只要您坚持使用这些规则进行代数运算，Galois字段就看起来完全像您熟悉的实数字段。
要学习如何进行算术运算（即实际在Galois字段中进行计算（使用实际数字进行计算），最简单的方法（特别是如果您已经熟悉模块化算术）从主要Galois字段$ GF（p）$开始。这些领域中的算术运算只是简单的普通加法和整数乘以一些素数$ p $的模。例如，在$ GF（3）$中，存在三个数字（$ 0 $，$ 1 $和$ 2 $），它们具有以下加法和乘法规则（及其可交换变体）：开始{对齐}
0 + 0＆= 0＆1 + 1＆= 2＆0 \ times 0＆= 0＆1 \ times 1＆= 1 \\
0 + 1＆= 1＆ 1 + 2＆= 0＆0 \时间1＆= 0＆1 \时间2＆= 2 \\
0 + 2＆= 2＆2 + 2＆= 1＆0 \时间2＆= 0＆ 2 \ times 2＆= 1 \\
\ end {aligned} $$
这里唯一不寻常的规则是$ 1 + 2 = 0 $，$ 2 + 2 = 1 $和$ 2 \ times 2 = 1 $;在通常的算术中，这些结果等于或大于$ 3 $，因此通过减去$ 3 $来“包装”。从这些规则，我们还可以确定逆。原来$ -0 = 0 $，$-1 = 2 $和$ -2 = 1 $（因为$ 1 + 2 = 0 $）和$ 1/1 = 1 $和$ 1/2 = 2 $（因为$ 2 \ times 2 = 1 $），因此它们确实存在并且属于该字段。 （作为练习，我将保留所有的逆函数都是唯一的，并且这些规则的确也满足所有其他领域公理。）
为什么我们需要$ p作为素数，然后？好吧，事实证明，如果数字$ m $不是质数，那么某些数字将不会以$ m $取模的乘法逆：例如，没有整数$ a $使得$ 2 \ times a = 1 \ pmod 4 $。因此，除非$ m $是素数，否则对$ m $取模的整数实际上不会形成一个字段（而只能是一个环）。形式为$ m = p ^ n $，对于一些质数$ p $和一些正整数$ n $，那么我们仍然可以通过更改有关加法和乘法的规则来保存内容。这就是有关向量和多项式的所有内容的来源。但是，您要记住的是，它们并没有真正代表任何增加的复杂性，而只是表示事物的另一种方式。从根本上讲，我们仍在处理一组$ p ^ n $数字以及在其上定义的一些算术运算-事实证明，例如，我们需要使用的乘法规则很容易描述至少在您还记得在高中也学过的多项式相乘和相乘（除法）规则的情况下，才能用一个多项式来标识字段中的每个数字。
因此，让我们从向量和加法开始。给定$ a \ in \ {0，\ dotsc，p ^ n-1 \} $中的数字，我们可以用$ n $ base- $ p $位$ a_0，\ dotsc，a_ {n -1} $，例如$$ a = a_0 + a_1 p + a_2 p ^ 2 + \ dotsb + a_ {n-1} p ^ {n-1}。$$
这是确切地讲，您将如何以二进制形式将$ 2 ^ n $表示为$ n $位的字符串。我们也可以将字符串称为向量，因为基本上就是向量：数字的有限长度序列。
现在，当您通常将数字逐位加在一起时，您需要保持跟踪进行。另一方面，将两个向量相加时比较简单：您只需将每个向量中的对应数字相加即可。现在，事实证明，要使字段公理在具有$ p ^ n $元素的字段中工作，我们将需要使用的加法规则正是这种“无进位加法”。例如，在$ GF（4）$中（我们通常写为$ GF（2 ^ 2）$来强调$ 4 = 2 ^ 2 $确实是质数），加法规则如下所示：
$$ \开始{对齐}
0 + 0＆= 0＆0 + 2＆= 2＆1 +1＆= 0＆1 + 3＆= 2＆2 + 3＆= 1 \ \
0 + 1＆= 1＆0 + 3＆= 3＆1 + 2＆= 3＆2 + 2＆= 0＆3 + 3＆= 0 \\
\ end {aligned} $$
如果以二进制形式写出来，它们看起来更合逻辑：
$$ \ begin {aligned}
00 + 00＆= 00＆ 00 + 10＆= 10＆01 + 01＆= 00＆01 + 11＆= 10＆10 + 11＆= 01 \\
00 + 01＆= 01＆00 + 11＆= 11＆01 + 10 ＆= 11＆10 + 10＆= 00＆11 + 11＆= 00 \\
\ end {aligned} $$
在这里您可以看到我们只是将$ 2 $取模的位数，并忽略任何进位。您可能还会将此“加法”规则识别为与按位XOR相同的操作。这不是$ GF（4）$独有的；任何$ n $的$ GF（2 ^ n）$元素都可以表示为$ n $位比特串，其加法表示为按位XOR。
因此，现在我们知道如何在$ GF（p ^ n）$中添加数字。那乘法呢？好吧，这就是多项式出现的地方。您可以看到，描述乘法规则的一种方法是想象数字$ a $的数字$ a_0，\ dotsc，a_ {n-1} $是多项式$$ a [x] = a_0 + a_1 x + a_2 x ^ 2 + \ dotsb + a_ {n-1} x ^ {n-1} $$与未知的$ x $。 （在这里，变量$ x $纯粹是一个正式的占位符；我们永远不会为它赋值，所以您永远不必担心“ $ x $是什么？”。它就在那里，以便我们可以使用高位学校代数规则，用于处理$ x $中的多项式。）
然后，将两个数字$ a $和$ b $相乘，我们只取它们各自的多项式$ a [x] $和$ b [ x] $，使用高中代数规则将它们相乘（对所有内部算术取模$ p $），然后取结果的系数。这一切都非常简单：请记住，多项式乘法也非常简单，就像普通的逐位乘法一样，只是再次没有进位。
但是等一下！乘法有时不会给我$ x ^ n $或更高阶的条件吗？如果我将它们包含在数字字符串中，那会不会导致数字大于$ p ^ n-1 $？
好吧，是的。这就是为什么要采取另一个步骤的原因：乘法之后，我们需要对结果进行模降低，以合适的多项式为模（具体而言，是阶为$ n $的不可约单项式）。也就是说，我们将乘积的结果除以该减少多项式（我们可以再次用高中多项式长除法进行除法），再次记住对系数$ p $进行所有算术运算，并保持余数（等于或小于$ x ^ {n-1} $）。当然，实际上，在乘法过程中进行归约通常更有效，因此您不需要存储冗长的中间结果。
好吧，那简化多项式从哪里来？好吧，事实证明，我们在选择它方面有一定的自由度，因为通常有几个可以使用的多项式。每个字段都将给出不同的乘法规则，尽管如此构造的所有字段（更一般地说，所有带有$ p ^ n $个元素的有限字段）都是同构的，在某种意义上，对于任何两个Galois字段$ A $和$ B $ of $ p ^ n $个元素，有一个可逆函数$ f：A \ to B $将一个字段映射到另一个字段，因此$ f（a + b）= f（a）+ f（b）$和$ f（a \ times_A b）= f（a）\ times_B f（b）$，其中$ \ times_A $和$ \ times_B $表示两个字段的乘法运算符。因此，当我们只关心字段的一般代数性质，而不关心数字的具体表示形式时，通常会说$ p ^ n $阶的“ the Galois字段”，即使它可能具有多种表示形式。
如果要求您在特定的Galois字段中计算某些内容，通常会为您提供归约多项式。例如，如果您正在编写AES实现，它将使用$ GF（2 ^ 8）$和约数多项式$ x ^ 8 + x ^ 4 + x ^ 3 + x + 1 $（其中，因为$ p = 2 $，所有系数均为$ 0 $或$ 1 $）。
如果您选择自己的表示形式，因此是自己的约简多项式，则通常应尝试选择使计算容易的事物，但要遵守上述不可约性约束。通常，这意味着选择具有尽可能少的非零系数，并且所有这些系数都以低阶项出现的东西（$ x ^ n $项除外，多项式必须具有$ 1 $的系数） monic，当然是$ n $的订单。）
我可以更详细地介绍如何在二进制Galois字段$ GF（2 ^ n）$中实现乘法，因为我上面编写的内容仍然处于相当抽象的水平，并且尤其是对于来自编程背景的人-理论通常比实际代码复杂（或至少看起来像那样）。但是，老实说，我自己对事物的理论方面比较熟悉，无论如何，这个答案已经足够长了。 Wikipedia确实有一篇关于有限域算术的不错的文章，但是您可以从这里开始。
哦，对于一些素数$ p $和$ p ^ n $而言不是$ p ^ n $的Galois字段呢？正整数$ n $？好吧，事实证明并没有任何东西-如果元素的数量具有两个不同的素数，则无法满足领域公理。所以，a，没有$ GF（6）$或$ GF（10）$这样的东西。
评论
$ \ begingroup $
这是一个了不起的答案。我明白了！ :)
$ \ endgroup $
–多项式
2012年5月27日在9:16
$ \ begingroup $
某些答案使我对“特别是$ n $阶不可约的单项多项式”中陈述的事实感到不舒服。这样的多项式可以是原始的，也可以不是原始的，并且会创建两类$ GF（p ^ n）$表示形式作为$ [0，p-1] $中$ n $整数的向量：使用原始多项式的那些其他但它们仍然都是同构的，我发现这违反直觉。是否有一种简单的方法来表征两种表示形式的属性？
$ \ endgroup $
–fgrieu♦
2012-12-16 20:36
$ \ begingroup $
1 + 3 mod 2 = 0，但是您得到了：1 + 3 mod 2 = 2，因为答案中的1 + 3 = 2。它如何涵盖“以2为模加总”的加法规则？我错过了什么？我也不能用“回合”附加规则来计算。如何计算？
$ \ endgroup $
–ampika
17年5月13日在0:23
$ \ begingroup $
@ampika：要在$ GF（p ^ n）$中添加数字，请将它们写在基数$ p $中，然后将相应的数字以$ p $模加在一起，而忽略进位。因此，例如，要将$ 1 $和$ 3 $加到$ GF（2 ^ 2）$中，您首先将它们写成$ 1 = 01_2 $和$ 3 = 11_2 $的二进制形式，然后将$ 2 $取二进制数：$ 01_2 $和$ 11_2 $的前两位是$ 0 $和$ 1 $，而$ 0 + 1 \ equiv 1 \ pmod2 $，因此结果的第一位是$ 1 $，而第二位是$ 1 $和$ 1 $和$ 1 + 1 \ equiv 0 \ pmod2 $，因此结果的第二位数为$ 0 $。因此，最终结果是$ 10_2 = 2 $。
$ \ endgroup $
–伊尔马里·卡洛宁
17年5月13日在9:13
$ \ begingroup $
老实说，我喜欢阅读每个单词！
$ \ endgroup $
– achabahe
17年6月3日在16:00
#2 楼
我认为您所说的内容有些空白和误解。有限域或伽罗瓦域$ GF（p ^ n）$是$ p ^ n $ $ n $维矢量的集合。在这里，$ p $是质数，矢量中的每个坐标为$ [0，p-1] $范围内的整数；即$ GF（p）$的元素。因此，GF（p）$$
中的
$$ \ mathbf A =（a_0，a_1，\ ldots，a_ {n-1}），~~ a_i \是$ GF（ p ^ n）$。
由于每个$ a_i $有$ p $个选择，因此我们有$ p ^ n $个向量。
形式上，$ GF（p ^ n）$的元素构成一个向量空间，在$ GF（p）$之上。因此，该字段中的加法和减法是矢量加法和减法，其中每个坐标中的算术以模$ p $进行，即以$ GF（p）$为模。
乘以标量，即$ GF（p）$的元素也很简单。如果GF（p）$中的$ b \，则
$$ b \ mathbf A =（ba_0，ba_1，\ ldots，ba_ {n-1}）。$$
元素的乘法和除法$ GF（p ^ n）$
的解释和理解有些棘手。我们可以将
多项式$ A（x）$与每个元素关联
$ \ mathbf A $其中
$$ \ mathbf A =（a_0，a_1，\ ldots，a_ {n- 1}）\ leftrightarrow A（x）= a_0 + a_1x + a_2x ^ 2 + \ cdots + a_ {n-1} x ^ {n-1}。$$
然后，$ \ mathbf A \ cdot \ mathbf B = \ mathbf C $其中
$$ \ mathbf C \ leftrightarrow C（x）= A（x）B（x）\ bmod M（x）$$
其中$ M（x） = m_nx ^ n + m_ {n-1} x ^ {n-1} + \ cdots + m_1 x + m_0 $是阶数为n的不可约多项式，系数为$ GF（ p）$。在这里，不可约意味着不能将$ M（x）$
分解为两个多项式，两个多项式的度数为<< n $，并且系数为$ GF（p）$。为方便起见，通常将$ M（x）$选择为单项多项式，这意味着$ x ^ n $
的系数为$ 1 $。我假设您知道$ A（x）B（x）\ bmod M（x）$意味着我们将
$ A（x）$和$ B（x）$相乘即可得到次数的多项式设为$ 2n-2 $，
除以$ M（x）$，然后取余多项式，即
度<< n $，如$ C（x）$。
求除法，因为$ B（x）$和$ M（x）$不能有一个
公因数正数，则它们最大的公约数
是$ 1 $。 Bezout的身份表明gcd $ 1 $可表示为
$ 1 = B（x）D（x）+ E（x）M（x）\ Rightarrow B（x）D（x）\ equiv 1 \ bmod M（x）$$
，因此$ D（x）$充当$ B（x）$的乘法逆。
因此，除法定义为乘以该逆：
$$ \ mathbf A / \ mathbf B = \ mathbf A \ cdot \ mathbf B ^ {-1}
= \ mathbf A \ cdot \ mathbf D \ leftrightarrow
A（x）D（x ）\ bmod M（x）。$$
最后，关于您的陈述“我看过提到这些字段是双射的”，请注意，字段是集合，而不是映射。
映射或函数可以是双射的，集合不能。
可能要传达给您的是
正在计算的函数是双射映射>从$ GF（p ^ n）$到自身：$ GF（p ^ n）$的每个元素都映射到$ GF（p ^ n）$中的唯一图像上。这样的
映射的一个简单示例是$ T：\ mathbf A \到T（\ mathbf A）= \ mathbf A \ cdot \ mathbf B $，其中
$ \ mathbf B $是固定的非零$ GF（p ^ n）$的元素。因此，
正向映射将$ \ mathbf A $发送给$ \ mathbf A \ cdot \ mathbf B $
，而反向映射将$ \ mathbf G $发送给$ \ mathbf G \ cdot \ mathbf B ^ {-1}
= \ mathbf G \ cdot \ mathbf D. $当然，对于密码
应用程序，人们可能想使用比此简单函数更复杂的双射
函数。插图。在$ GF（2 ^ 8）$上运行的s-box将字节（$ GF（2 ^ 8）$的元素）
发送到字节。
评论
$ \ begingroup $
<< * snip * >>-我已将此评论作为对问题的更新。
$ \ endgroup $
–多项式
2012年5月25日5:43
#3 楼
除了其他一些答案之外，在理解有限域或与此有关的任何代数结构方面，对我最大的帮助是。为此，我发现Sage不可或缺。所以，看看Sage中的Galois Fields就像这样：
可以继续下去。 Sage是基于python构建的，因此在大多数情况下，它使用python语法。
从中您可以看到该字段的工作方式。该字段由度为$ n-1 $的多项式组成。多项式中的系数是对$ p $取模的整数。现在，它在计算机中的实际表示方式可能有所不同。对于$ GF（2 ^ 8）$，将单个元素的所有系数（为$ 0 $或$ 1 $）存储在单个字节的内存中非常容易。 $ p> 2 $的其他字段不同。您可以将它们作为多项式系数的向量存储在计算机中。
#4 楼
好的，所以您可能知道领域是值得研究的有趣结构……它们是算术效果很好的地方。大多数加密系统严重依赖数字，通常必须从某个字段中获取数字才能计算出结果。现在有许多字段包含无限多个元素，例如$ \ mathbb {Q}，\ mathbb { R}，\ mathbb {C} ... $，但有限字段可能是什么样？
情况实际上很简单，事实证明这样的字段只能包含$ p ^ n $元素，其中$ p $是一些质数，$ n $是一些正整数。同样对于$ p，n $的每种可能性，都只存在一个大小为$ p ^ n $的字段（至同构，即以一种连贯的方式对元素进行重新标记）。 $ GF（p ^ n）$或$ \ mathbb {F} _ {p ^ n} $。它只是“订单域$ p ^ n $”的一种表示法。注意$ \ mathbb {F} _p $只是整数mod $ p $，这是我们已经知道的字段。
现在我们将如何构造$ \ mathbb {F} _ {p ^ n } $一般？好了，使用一些抽象代数，我们可以构造如下字段：
1）制作一个度数为$ n $的多项式$ f $，它是不可约的mod $ p $。
2）考虑商环$ \ mathbb {F} _p [x] / \ langle f \ rangle $。这必须是一个字段，因为$ f $在$ \ mathbb {F} _ {p} $上是不可约的，并且由于$ f $具有度数$ n $，因此该字段也必须具有$ p ^ n $个元素。 />
3）因此，通过此类字段的唯一性$ \ mathbb {F} _ {p ^ n} \ cong \ mathbb {F} _p [x] / \ langle f \ rangle $。
因此，您可以通过使用此多项式商环（计算机可以轻松处理的东西）来实现域算术。
评论
$ \ begingroup $
虽然这是正确的，但我想它并没有太大帮助，因为它使用了一些更未知的术语，例如“商环”和“不可约多项式”。
$ \ endgroup $
–PaŭloEbermann
2012年5月27日晚上10:21
$ \ begingroup $
但是，肯定不包含这些术语的答案是“在地毯下面刷东西”吗？我不会在这里写有关有限域的书，而是将有限域的概念与多项式更易于理解。在我看来，原始张贴者知道实际上是什么领域，因此应该知道什么是戒指。商部分可能并不熟悉，但可以阅读有关该部分（或依赖于已经有实现这些方法的事实）。术语“不可约多项式”应该已经被理解了……但是要花几秒钟才能理解。
$ \ endgroup $
–fretty
2012年5月27日10:31
评论
有限的领域是一个引人入胜的主题，但是您从论坛上无法真正理解。我真的建议您读一本关于数论的书，并花一些时间。这将在您的余生中极大地帮助您。例如，我喜欢Victor Shoup撰写的“数论和代数的计算导论”。整本书以PDF格式提供，第20章讨论了“有限域”。如果您有较少的时间，请参阅[Neal Koblitz开设的数论和密码学课程]（amazon.com/Course-Number-Cryptography-Graduate-Mathematic$ GF（p ^ n）$是一组向量：该字段本身不执行任何计算，它只是存在并且没有输入也没有输出。例如，$ GF（2 ^ 8）$是$ 256 $ $ 8 $位字节的集合。要添加该字段的两个元素，您需要对两个字节进行逐位加和运算，取模$ 2 $（又称XOR）；在这种情况下，减法也是字节的异或。乘法（在我的答案中描述的形式）的实现起来比较复杂。对于更简单的方法，您需要了解有关有限域的更多信息（请参见SquareRootOfTwentyThree的答复中的参考资料）。
@DilipSarwate，字段不只是一组元素。它是一组带有运算的元素（通常称为加法和乘法，但不一定是您听到这些名称时的想法）。此外，这些运算必须满足certian属性（加法时关闭，乘法时关闭，加法和乘法时可交换等）
@mikeazo是的，我知道所有这些。我试图在可用的简短空间或注释中，使字段是函数的概念的OP失效。他似乎在想$ GF（\ cdot）$是一个函数，该函数应用于其参数$ p ^ n $可以创建其他函数。在这种情况下，关键是该字段本身不会做任何事情，并且它不是一个函数，而是一个集合。
@DilipSarwate，您是正确的，我现在知道您要去的地方。字段不是运算符。您可以将某些字段的元素表示为多项式，但是通常不使用该多项式作为运算符。