热门问题
时间线
聊天
视角

有限體運算

在有限域之内的算术 来自维基百科,自由的百科全书

Remove ads

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

不同的有限體有無限多種,它們的(英語:Cardinality)皆以 的形式表示,其中 是一個質數自然數。兩個元素數量相同的有限體稱做同構的 同時代表此有限體的特徵數,而 則是此有限體的維度

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

Remove ads

有效多項式表示

伽羅瓦體

元素有限體可以表示成,其中 GF 為伽羅瓦體(英語:Galois field)的縮寫。伽羅瓦體即為有限體的別稱,以紀念現代群論的重要奠基者——埃瓦里斯特·伽羅瓦[1]

一個簡單的例子是(也能可表示成),其中是一個質數是將正整數作以為模的模運算後所得的結構。換言之,我們可以對整數進行加法、減法、乘法的運算,接著再以模運算將結果簡化。因此其實也是一種

Remove ads

為例

中, 而不會等於,這是因為。而除法能理解為對其乘法反元素作乘法,並可以使用擴充版的輾轉相除法來計算。

為例

的加法為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}
Remove ads

加法和減法

加法減法可實施在加與減這兩則多項式,再而使用模除特徵值以簡化。

在一則特徵值為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 ...

計算機科學的諸多應用程式之中,特徵值為2的有限體運算被簡單化,稱之為GF(2n) 伽羅瓦體,使的這些領域在應用程式中,體現出一種特別大眾化的選擇。

Remove ads

乘法

乘法是在有限體之內,把乘積模除於,一則用來表示有限體的,簡約過的不可約多項式。 (換句話說, 乘法再跟上使用,簡約了的多項式充當除數的除法,然後餘數則是它們的乘積。) 符號 "•" 可以用作於在有限體之內的乘法。

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads