查看“︁有限域算术”︁的源代码

{{多個問題|
{{cleanup-jargon|time=2018-03-25T11:26:24+00:00}}
{{copyedit|time=2018-03-25T11:26:24+00:00}}
{{expand|time=2018-03-23T20:34:04+00:00}}

}}
{{NoteTA
|G1 = Math
|1 = zh-cn:域; zh-tw:體;
|2 = zh-cn:同态; zh-tw:同構;
|3 = zh-cn:算术; zh-tw:運算;
|4 = zh-hans:领域; zh-hant: 領域;
}}

'''有限體運算'''是[[抽象代數]]中的一個概念，尤指在[[有限體]]之中進行的[[算數|運算]]。其中[[有限體]]是一種[[體 (數學)|體]]，所以包含的[[元素 (數學)|元素]]數量是有限的。作為比較，[[無限體運算]]則指在有無限多[[元素 (數學)|元素]]的[[體 (數學)|體]](如[[有理數]])中的運算。

不同的[[有限體]]有無限多種，它們的[[勢 (數學)|勢]]({{lang-en|Cardinality}})皆以 <math>p^n</math> 的形式表示，其中 <math>\ p</math> 是一個[[質數]]； <math>n</math> 為[[自然數]]。兩個[[元素 (數學)|元素]]數量相同的[[有限體]]稱做[[同構|同構的]]。<math>p</math> 同時代表此有限體的[[特徵 (代數)|特徵數]]，而<math>\ n</math> 則是此有限體的[[向量空间的维数|維度]]。

[[有限體]]有許多不同的應用，包含[[編碼理論]]與線性[[分組碼|區塊碼]](例如[[BCH碼]]和[[里德-所羅門碼]])以及在[[密碼學]]中的[[演算法]](例如[[進階加密標準]])等不同领域的应用。

==有效多項式表示==
===伽羅瓦體===
有<math>\ p^n</math>個[[元素 (數學)|元素]]的[[有限體]]可以表示成<math>\ \mathrm{GF}(p^n)</math>，其中 GF 為'''伽羅瓦體({{lang-en|Galois field}}''')的縮寫。伽羅瓦體即為[[有限體]]的別稱，以紀念現代群論的重要奠基者——[[埃瓦里斯特·伽羅瓦]]<ref name=":0">{{Cite book|title=Math and mathematicians : the history of math discoveries around the world|last=C.|first=Bruno, Leonard|orig-year=1999|date=c. 2003|publisher=U X L|others=Baker, Lawrence W.|isbn=978-0787638139|location=Detroit, Mich.|page=[https://archive.org/details/mathmathematicia00brun/page/171 171]|oclc=41497065|url=https://archive.org/details/mathmathematicia00brun|url-access=registration}}</ref>。

一個簡單的例子是<math>\ \mathrm{GF}(p)</math>(也能可表示成<math>\ \mathbf{Z}/p\mathbf{Z}</math> 或 <math>\mathbb{F}_{p}</math>)，其中<math>\ p\ </math>是一個[[質數]]。<math>\ \mathrm{GF}(p)</math>是將正整數作以<math>\ p\ </math>為模的[[模算數|模運算]]後所得的結構。換言之，我們可以對[[整數]]進行加法、減法、乘法的運算，接著再以[[模算數|模運算]]將結果簡化。因此<math>\ \mathrm{GF}(p)</math>其實也是一種[[環 (代數)|環]]。

===以<math>\ \mathrm{GF}(5)</math>為例===
在<math>\ \mathrm{GF}(5)</math>中，<math>4 + 3 = 2</math> 而不會等於<math>\ 7</math>，這是因為<math>\ 7_(mod\ 5) = 2</math>。而除法能理解為對其[[反元素|乘法反元素]]作乘法，並可以使用[[擴展歐幾里得算法|擴充版的輾轉相除法]]來計算。

===以<math>\ \mathrm{GF}(2)</math>為例===
<math>\ \mathrm{GF}(2)</math>的加法为[[异或门|XOR]]，而乘法是[[与门|AND]]。由于唯一具有[[倒数]]的元素是数字1，除法则是[[恆等函數]]。

GF(''p<sup>n</sup>'')的元素可表示为，在GF(''p'')之上严格小于''n''[[冪|次数]]的[[多項式|多项式]]。运算则实行在先模除''R''，而''R''是一则在GF(''p'')之上，拥有''n''次数的[[不可约多项式]]，例如运用[[多项式长除法]]。两则多项式''P''和''Q''则按常规运算；乘法则按如下进行：先按常规计算{{nowrap|1=''W'' = ''P''⋅''Q''}}，然后计算模除''R''之后的余项(存在有更方便方法)。

当素数是2时，一般按常规可以把GF(''p<sup>n</sup>'')的元素表示为[[二进制|二进制数]]，按对应元素的[[二进制]]表示，[[多项式]]的每一项表示为一[[位元|比特]]的，相对应元素的二进制数位，并且括号( "{"和"}" )或类似的分隔符也普遍附加于这些二进制数，或对应它们的[[十六进制]]的同等数，以表明数值确确是域内的一则元素。例如，下列数都在具有2的特征下持有相同的数值。

;多项式<nowiki>:  </nowiki> ''x''<sup>6</sup> + ''x''<sup>4</sup> + ''x'' + 1
;二进制<nowiki>:      </nowiki>{01010011}
;十六进制<nowiki>: </nowiki>{53}

==加法和减法==
[[加法]]和[[减法]]可实施在加与减这两则[[多项式]]，再而使用[[模除]]其[[特征 (代数)|特征值]]以简化。

在一则特征值为2的有限域之中，加法模2，减法模2，如同使用[[异或门|XOR]]，因此：

;多项式：(''x''<sup>6</sup> + ''x''<sup>4</sup> + ''x'' + 1) + (''x''<sup>7</sup> + ''x''<sup>6</sup> + ''x''<sup>3</sup> + ''x'') = ''x''<sup>7</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + 1
;二进制：	{01010011} + {11001010} = {10011001}
;十六进制：{53} + {CA} = {99}

在常规的[[无限域]]的[[多项式]]的加法下，计算之和需要包含单项 2''x''<sup>6</sup>，但在[[有限域]]的加法下，0''x''<sup>6</sup>则被去掉，因为其计算结果被模2所消除。

下列是一则包含有对于一些多项式的，常规代数计算和与特征值为2的[[有限域]]的计算和，一同列出的图表。

{| class="wikitable"
 ! ''p''<sub>1</sub>
 ! ''p''<sub>2</sub>
 ! ''p''<sub>1</sub> + ''p''<sub>2</sub> (normal algebra)
 ! ''p''<sub>1</sub> + ''p''<sub>2</sub> in GF(2<sup>''n''</sup>)
 |- 
 | ''x''<sup>3</sup> + ''x'' + 1
 | ''x''<sup>3</sup> + ''x''<sup>2</sup>
 | 2''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x'' + 1
 | ''x''<sup>2</sup> + ''x'' + 1
 |-
 | ''x''<sup>4</sup> + ''x''<sup>2</sup>
 | ''x''<sup>6</sup> + ''x''<sup>2</sup>
 | ''x''<sup>6</sup> + ''x''<sup>4</sup> + 2''x''<sup>2</sup>
 | ''x''<sup>6</sup> + ''x''<sup>4</sup>
 |-
 | ''x'' + 1
 | ''x''<sup>2</sup> + 1
 | ''x''<sup>2</sup> + ''x'' + 2
 | ''x''<sup>2</sup> + ''x''</tr>
 |-
 | ''x''<sup>3</sup> + ''x''
 | ''x''<sup>2</sup> + 1
 | ''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x'' + 1
 | ''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x'' + 1
 |-
 | ''x''<sup>2</sup> + ''x''
 | ''x''<sup>2</sup> + ''x''
 | 2''x''<sup>2</sup> + 2''x''
 | 0
 |}

在[[计算机科学]]的诸多应用程序之中，特征值为2的有限域运算被简单化，称之为GF(2<sup>''n''</sup>) [[伽罗瓦域]]，使的这些领域在应用程序中，体现出一种特别大众化的选择。

==乘法==
<!-- 请不要更改这则有限域案例，（x8 + x4 + x3 + x + 1); Rijndael加密法的页面链接在此，大家可以使用这篇文章认识得到部分协助，认识了解Rijndael有限域。-->
乘法是在有限域之内，把乘积模除于，一则用来表示有限域的，简约过的[[不可约多项式]]。 (换句话说， 乘法再跟上使用，简约了的多项式充当除数的除法，然后余数则是它们的乘积。) 符号 "•" 可以用作于在有限域之内的乘法。

=== Rijndael有限域 ===
[[高级加密标准|Rijndael]]（Rijndael的發音近於"Rhine doll")使用包含256个元素的持有特征值是2的有限域， 同时可被称之为[[伽罗瓦域]]'''GF'''(2<sup>8</sup>)。在乘法上它依赖下列简约多项式：

:''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x'' + 1

例如：{53} • {CA} = {01}，因为在Rijndael域中：

: &nbsp;&nbsp;&nbsp;(''x''<sup>6</sup> + ''x''<sup>4</sup> + ''x'' + 1)(''x''<sup>7</sup> + ''x''<sup>6</sup> + ''x''<sup>3</sup> + ''x'')

: = (''x''<sup>13</sup> + ''x''<sup>12</sup> + ''x''<sup>9</sup> + '''x<sup>7</sup>''') + (''x''<sup>11</sup> + ''x''<sup>10</sup> + '''x<sup>7</sup>''' + ''x''<sup>5</sup>) + (''x''<sup>8</sup> + '''x<sup>7</sup>''' + ''x''<sup>4</sup> + ''x''<sup>2</sup>) + ('''x<sup>7</sup>''' + ''x''<sup>6</sup> + ''x''<sup>3</sup> + ''x'')

: = ''x''<sup>13</sup> + ''x''<sup>12</sup> + ''x''<sup>9</sup> + ''x''<sup>11</sup> + ''x''<sup>10</sup> + ''x''<sup>5</sup> + ''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>2</sup> + ''x''<sup>6</sup> + ''x''<sup>3</sup> + ''x''

: = ''x''<sup>13</sup> + ''x''<sup>12</sup> + ''x''<sup>11</sup> + ''x''<sup>10</sup> + ''x''<sup>9</sup> + ''x''<sup>8</sup> + ''x''<sup>6</sup> + ''x''<sup>5</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x''

与

: ''x''<sup>13</sup> + ''x''<sup>12</sup> + ''x''<sup>11</sup> + ''x''<sup>10</sup> + ''x''<sup>9</sup> + ''x''<sup>8</sup> + ''x''<sup>6</sup> + ''x''<sup>5</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x'' 模除 ''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x''<sup>1</sup> + 1 = (11111101111110 模 100011011) = {3F7E mod 11B} = {01} = 1 ([[十进制]])，同时可被[[long division|长除法]]所表示，(使用[[二进制]]注释。注意 [[异或门|XOR]]在例题中的应用，而不是常规运算中的减法。)：

          <u>               </u>
           11111101111110 (mod) 100011011
          <u>^100011011     </u>
            1110000011110
           <u>^100011011    </u>
             110110101110
            <u>^100011011   </u>
              10101110110
             <u>^100011011  </u>
               0100011010
              <u>^00000000  </u>
                100011010
               <u>^100011011 </u>
                 00000001

（[[十六进制]]数字{53}和{CA}相互是[[倒数|乘法逆元]]，由于它们的乘积是[[1]]。)
[[Category:域论]]
[[Category:环论]]
[[Category:代数结构]]