有限域算术

维基百科,自由的百科全书
跳到导航 跳到搜索

数学之中,有限域算术是一种在有限域之内的算术,因为仅包括有限数量的元素,而有限域算术则相对于无限域算术,后者是包括无限数量的元素的算术(如在有理数之下的算术)。

由于并没有任何有限域是无限的,因此存在着无限多个不同的有限域。它们的需要是能够在pn的形式下,这其中的p是一则素数,而n则是一则正整数,同时两个持有等量的有限域可以构成同构。素数p被称之为有限域的特征,而正整数n则被称之为有限域的向量空间的维数,凌驾于它的最初域之上,最初域为最小的包括1F的子域

有限域应用于各种领域,这其中包括在线性分组码之内的编码理论,譬如BCH码里德-所罗门码,还有在密码学之中的演算法,比如Rijndael加密法之下的加密算法。

实效多项式表示[编辑]

持有pn元素的有限域可由GF(pn)(同时可被, Fpn})所表示,被命名为伽罗瓦域, 以荣誉有限域学说的创始者埃瓦里斯特·伽罗瓦. GF(p)(同时可表示为Z/pZ, , 或Fp), 其中p为一则素数, GF(p)简明称之为就是,一个整数群模除 p之后,而得到的结果. 这表明是,可以在整数范围中,先行执行常规运算(加法,减法,乘法), 然后模除p而以简化,举例说明, 在GF(5)内, 4 + 3 = 7被简化为2,因为是7模除5的结果。 除法则是在模除p的倒数上实施乘法, 并且可以选择使用扩展欧几里得算法来计算。

一则特别的范例就是GF(2), 其加法为XOR,而乘法是AND. 由于唯一具有倒数的元素是数字1,除法则是恆等函數

GF(pn)的元素可表示为,在GF(p)之上严格小于n次数多项式。运算则实行在先模除R,而R是一则在GF(p)之上,拥有n次数的不可约多项式, 例如运用多项式长除法。两则多项式PQ则按常规运算;乘法则按如下进行: 先按常规计算W = PQ, 然后计算模除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。)