有限域算术
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() |
有限體運算是抽象代數中的一個概念,尤指在有限體之中進行的運算。其中有限體是一種體,所以包含的元素數量是有限的。作為比較,無限體運算則指在有無限多元素的體(如有理數)中的運算。
不同的有限體有無限多種,它們的勢(英語:Cardinality)皆以 的形式表示,其中 是一個質數; 為自然數。兩個元素數量相同的有限體稱做同構的。 同時代表此有限體的特徵數,而 則是此有限體的維度。
有限體有許多不同的應用,包含編碼理論與線性區塊碼(例如BCH碼和里德-所羅門碼)以及在密碼學中的演算法(例如進階加密標準)等不同领域的应用。
有效多項式表示
伽羅瓦體
有個元素的有限體可以表示成,其中 GF 為伽羅瓦體(英語:Galois field)的縮寫。伽羅瓦體即為有限體的別稱,以紀念現代群論的重要奠基者——埃瓦里斯特·伽羅瓦[1]。
一個簡單的例子是(也能可表示成 或 ),其中是一個質數。是將正整數作以為模的模運算後所得的結構。換言之,我們可以對整數進行加法、減法、乘法的運算,接著再以模運算將結果簡化。因此其實也是一種環。
以為例
在中, 而不會等於,這是因為。而除法能理解為對其乘法反元素作乘法,並可以使用擴充版的輾轉相除法來計算。
以為例
的加法为XOR,而乘法是AND。由于唯一具有倒数的元素是数字1,除法则是恆等函數。
GF(pn)的元素可表示为,在GF(p)之上严格小于n次数的多项式。运算则实行在先模除R,而R是一则在GF(p)之上,拥有n次数的不可约多项式,例如运用多项式长除法。两则多项式P和Q则按常规运算;乘法则按如下进行:先按常规计算W = P⋅Q,然后计算模除R之后的余项(存在有更方便方法)。
当素数是2时,一般按常规可以把GF(pn)的元素表示为二进制数,按对应元素的二进制表示,多项式的每一项表示为一比特的,相对应元素的二进制数位,并且括号( "{"和"}" )或类似的分隔符也普遍附加于这些二进制数,或对应它们的十六进制的同等数,以表明数值确确是域内的一则元素。例如,下列数都在具有2的特征下持有相同的数值。
- 多项式: x6 + x4 + x + 1
- 二进制: {01010011}
- 十六进制: {53}
加法和减法
加法和减法可实施在加与减这两则多项式,再而使用模除其特征值以简化。
在一则特征值为2的有限域之中,加法模2,减法模2,如同使用XOR,因此:
- 多项式:(x6 + x4 + x + 1) + (x7 + x6 + x3 + x) = x7 + x4 + x3 + 1
- 二进制: {01010011} + {11001010} = {10011001}
- 十六进制:{53} + {CA} = {99}
在常规的无限域的多项式的加法下,计算之和需要包含单项 2x6,但在有限域的加法下,0x6则被去掉,因为其计算结果被模2所消除。
下列是一则包含有对于一些多项式的,常规代数计算和与特征值为2的有限域的计算和,一同列出的图表。
p1 | p2 | p1 + p2 (normal algebra) | p1 + p2 in GF(2n) |
---|---|---|---|
x3 + x + 1 | x3 + x2 | 2x3 + x2 + x + 1 | x2 + x + 1 |
x4 + x2 | x6 + x2 | x6 + x4 + 2x2 | x6 + x4 |
x + 1 | x2 + 1 | x2 + x + 2 | x2 + x |
x3 + x | x2 + 1 | x3 + x2 + x + 1 | x3 + x2 + x + 1 |
x2 + x | x2 + x | 2x2 + 2x | 0 |
在计算机科学的诸多应用程序之中,特征值为2的有限域运算被简单化,称之为GF(2n) 伽罗瓦域,使的这些领域在应用程序中,体现出一种特别大众化的选择。
乘法
乘法是在有限域之内,把乘积模除于,一则用来表示有限域的,简约过的不可约多项式。 (换句话说, 乘法再跟上使用,简约了的多项式充当除数的除法,然后余数则是它们的乘积。) 符号 "•" 可以用作于在有限域之内的乘法。
Rijndael有限域
Rijndael(Rijndael的發音近於"Rhine doll")使用包含256个元素的持有特征值是2的有限域, 同时可被称之为伽罗瓦域GF(28)。在乘法上它依赖下列简约多项式:
- x8 + x4 + x3 + x + 1
例如:{53} • {CA} = {01},因为在Rijndael域中:
- (x6 + x4 + x + 1)(x7 + x6 + x3 + x)
- = (x13 + x12 + x9 + x7) + (x11 + x10 + x7 + x5) + (x8 + x7 + x4 + x2) + (x7 + x6 + x3 + x)
- = x13 + x12 + x9 + x11 + x10 + x5 + x8 + x4 + x2 + x6 + x3 + x
- = x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x
与
- x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x 模除 x8 + x4 + x3 + x1 + 1 = (11111101111110 模 100011011) = {3F7E mod 11B} = {01} = 1 (十进制),同时可被长除法所表示,(使用二进制注释。注意 XOR在例题中的应用,而不是常规运算中的减法。):
11111101111110 (mod) 100011011 ^100011011 1110000011110 ^100011011 110110101110 ^100011011 10101110110 ^100011011 0100011010 ^00000000 100011010 ^100011011 00000001
(十六进制数字{53}和{CA}相互是乘法逆元,由于它们的乘积是1。)
- ^ C., Bruno, Leonard. Math and mathematicians : the history of math discoveries around the world
. Baker, Lawrence W. Detroit, Mich.: U X L. c. 2003: 171 [1999]. ISBN 978-0787638139. OCLC 41497065.