畢設學習過程中得學習筆記
參考書是密碼編碼學與網絡安全

---

整除

b整除a，即是a/b沒有余數，即為b|a，稱b為a的因子

整數整除的性質

①若a|1，則 a = ±1.
②若a|b，且b|a，則 a = ±b。
③任意非零數b整除0.
④若a|b，b|c，則a|c
⑤若b|g，b|h，則對任意整數m，n，有b|(mg+nh)

歐幾里得算法

歐幾里得算法基于定理：

對于任意非負整數a和任意正整數b，

gcd (a，b) = gcd (b，a mod b)

定義1：兩個整數稱為互素的，如果它們唯一的正整數公因子是1。

最大公因子：對于整數a和b，能夠同時整除a和b的最大整數是a和b的最大公因子，記為gcd(a，b)。定義gcd(0，0) = 0。

因此如果 gcd(a，b) = 1，那么a和b互素。

求最大公因子
設有整數a，b，使得 d = gcd(a，b)。因為要求的最大公因子是正整數，所以gcd(a，b)=gcd(|a|，|b|)，因此假設a≥b>0。
現在用b除a，則a= q₁ x b + r₁，0≤r₁<b。
若r₁=0，則b|a，d=gcd(a，b)=b。
若r₁≠0，由整除性質⑤，d|a，d|b，那么d|(a-q₁ x b)，因此d|r₁。
而對任意整數c，若c|b，c|r₁，那么c|(q₁ x b+r₁)=c|a，又d=gcd(a，b)，則有c≤b，因此d=gcd(b，r₁)。
因為b＞r₁，用r₁除b，則b= q₂ x r₁ + r₂，0≤r₂＜r₁。
和前面一樣分為r₂=0和r₂≠0討論，這樣輾轉相除直到除法過程中余數為0。

模運算

如果a是整數，n是正整數，則定義a模n是a除以n所得的余數。整數n稱為模數。
如果(a mod n) = (b mod n)，則稱整數a和b是模n同余的。表示為a≡b(mod n)

同余的性質

①如果n|(a - b)，那么a≡b(mod n)。
②a≡b(mod n)隱含b≡a(mod n)。
③a≡b(mod n)，b≡c(mod n)隱含a≡c(mod n)。

①證明：
如果n|(a - b)，那么存在某個k使得(a-b)=kn。于是有a=b+kn。
因此(a mod n) = (b + kn除以n的余數) = (b除以n的余數) = (b mod n)。

模算術運算

性質：

①[ (a mod n) + (b mod n) ] mod n = (a + b) mod n
②[ (a mod n) - (b mod n) ] mod n = (a - b) mod n
③[ (a mod n) x (b mod n) ] mod n = (a x b) mod n

和普通算術一樣，冪運算可通過重復乘法實現

以模8運算為例

模運算中，整數x的加法逆元素是使(x + y)mod n = 0的y值，乘法逆元素是使(x * y)mod n = 1 mod n的y值

定義：比n小的非負整數集合：

稱為剩余類集，或模n的剩余類。

可以將模n的剩余類表示為[0], [1], [2], … , [n-1]，其中[r]={a：a是一個整數，a≡r(mod n)}

在剩余類的所有整數中，通常用最小非負整數代表這個剩余類。尋找與k是模n同余的最小非負整數的過程，稱為模n的k約化。

剩余類集Z_n是有乘法單位元的交換環。

模運算的加法逆元存在性和普通運算是一致的，然而乘法逆元存在性與普通運算有所區別。一般來說，如果一個整數與n互素，那么它在Z_n中有一個乘法逆元。

擴展的歐幾里得算法

對于給定的整數a和b，擴展的歐幾里得算法不僅計算出最大公因子d，而且還有另外兩個整數x和y，滿足如下方程：

ax + by = d = gcd (a，b)

x和y有相反的正負號。一般地，可以證明對于兩個給定的整數a和b，ax+by的最小正整數等于gcd(a，b)。

群、環、域

群

群G，是定義了一個二元運算的集合，記為{G，·}，G中每一個序偶(a，b)通過運算生成G中的元素(a，b)。
滿足以下公理：

①封閉性：如果a和b都屬于G，則a·b也屬于G。
②結合律：對于G中任意元素a、b、c，都有a·(b·c)=(a·b)·c成立。
③單位元：G中存在一個元素e，對于G中任意元素a，都有a·e=e·a=a成立。
④逆元：對于G中任意元素a，G中都存在一個元素a‘，使得下式成立a·a’=a’·a=e。

如果一個群的元素是有限的，則該群稱為有限群。并且群的階就等于群中元素的個數。否則，稱該群為無限群。

一個群若滿足以下條件，則成為交換群，也叫阿貝爾群：

⑤交換律：對于G中任意元素a、b，都有a·b=b·a成立。

當群中的運算符是加法時，其單位元是0；a的逆元是-a；并且定義減法為：a-b=a+(-b)。

定義冪運算為重復運用群中的運算，如a3=a·a·a。并且定義a⁰=e作為單位元；a^-n=(a’)ⁿ,其中a’是a在群內的逆元。

循環群： 群中的每一個元素都是一個固定元素a(a∈G)的冪a^k(k為整數)。

元素a生成了群G，或者說a是群G的生成元。
循環群總是交換群，可能是有限群或無限群。

環

環R，記為{R，+，x}，是一個有兩個二元運算的集合，對于R中任意元素a、b、c滿足以下公理：

R關于加法是一個交換群；因此R滿足從上述①-⑤的所有原則。
乘法的封閉性：如果a和b都屬于R，則ab也屬于R。
乘法的結合律：對于R中任意元素a、b、c，有 a(bc)=(ab)c成立。
分配律：對于R中的任意元素a、b、c，下面兩個式子總成立 a (b+c) = ab + ac; (a+b) c = ac + bc

實數上所有n階方陣的集合關于加法和乘法構成一個環。
環如果還滿足以下條件，則被稱為交換環：

乘法的交換律：對于R中任意元素a、b，有ab=ba成立。

偶整數集合記為S，在普通加法和乘法運算下是交換環。而矩陣運算不滿足交換律，所以上面的n階方陣集合就不是交換環。整數{0，1，…，n-1}的集合Z 加上模n的算術運算構成一個交換環。

滿足以下公理的交換環，稱為整環：

乘法單位元：在R中存在元素1，使得對于R中的任意元素a，有a1=1a=a成立。
無零因子：如果有R中元素a、b，且ab=0，則必有a=0或b=0。

將普通加法和乘法運算下的整數集合記為S，則S是一個整環。

域

域F，記為{F，+，x}，是有兩個二元運算的集合，對于F中的任意元素a、b、c滿足以下公理：

F是一個整環，因此F滿足整環的所有原則。
乘法逆元：對于F中的任意元素a(除0以外)，F中都存在一個元素a^-1使得下式成立：aa^-1 = (a^-1)a = 1

有限域GF( p )(伽羅華域Galois Fields)

有限域的階(元素的個數)必須是一個素數的冪pⁿ，n為正整數。(后面討論為什么p必須是素數)
階為pⁿ的有限域一般記為GF(pⁿ)，主要研究兩種特殊情形：n=1時的有限域GF( p )，它和n>1的有限域相比有著不同的結構；另一種是GF(2ⁿ)形式的有限域。

階為p的有限域

給定一個素數p，元素個數為p的有限域GF（p）被定義為整數{0，1，…，p-1}的集合Z，其運算為模p的算術運算。
在GF（p）中加法和乘法就是普通加法和乘法后再對結果取模p。
減法是根據加法來定義的，a-b=a+(-b)。（-b是b的逆元）
除法根據乘法來定義，a/b=a x (b^-1)。這里需要用到域的乘法逆元的原則，容易知道GF（p）的單位元e=1，那么乘法逆元就是對GF（p）的一個數a，
a x a^-1=1（mod p）。
因此對于GF（p）中a除以b就是a / b=a x (b^-1)=c，滿足b x c=a（mod p）的這個數c就是a除以b的結果。
p為什么一定是素數。
因為根據之前的討論，對于乘法逆元的存在性，模運算與普通運算是不同的，必須有一個附加條件，GF（p）定義的集合Z中的任一整數a有乘法逆元當且僅當a與p互素。所以當p為素數，GF（p）中的所有非零整數都有乘法逆元。從上面的模8運算可以看出，它并不是一個有限域，不是所有非零元素都有乘法逆元。

在GF（p）中求乘法逆元

對于數值較大的p，無法直接看出乘法逆元，可以通過擴展的歐幾里得算法求出乘法逆元。
對于正整數b<a，ax+by=d=gcd(a，b)，如果gcd(a，b)=1，那么b有模a的乘法逆元，且ax+by=1。又有
[(ax mod a) + (by mod a)] mod a=1 mod a
0 + (by mod a) = 1，通過擴展的歐幾里得算法，求出y=b^-1就是b的乘法逆元。

多項式運算

可以把多項式運算分為3種：
使用代數基本規則的普通多項式運算。
系數運算是模p運算的多項式運算，即系數在GF（p）中。
系數在GF（p）中，且多項式被定義為模一個n次多項式m(x)的多項式運算。
其中第三種在之后討論。

普通多項式運算

n次多項式的表達形式：

其中a_i是某個指定數集S中的元素，該數集叫做系數集，且a_n≠0。稱f(x)是定義在系數集S上的多項式。
零次多項式稱為常數多項式，僅僅是系數集中的一個元素。
如果a_n=1，那么對應的n次多項式稱為首1多項式。
變元x稱為不定元。
多項式運算包括加法，減法和乘法，當系數集S是域時，可以定義除法。注意整數集不是域，不支持多項式除法運算。

系數在Z_p中的多項式運算

系數是域F的元素的多項式稱為域F的多項式，
對于域上的多項式，除法可以定義為：給定n次多項式f(x)和m次多項式
g(x)，(m≤n)，如果用g(x)除f(x)，我們得到一個商q(x)和一個余數r(x)，滿足如下關系式：f(x)=q(x)g(x)+r(x)
其中f(x)是n次，g(x)m次，q(x)n-m次，r(x)≤m-1。如果r(x)=0，可以說g(x)整除f(x)，寫為g(x)|f(x)；也可以說g(x)是f(x)的一個因式。
其中GF(2)上的多項式很有意義，在GF(2)上的多項式運算，加法等價于XOR運算，乘法等價于邏輯與運算，并且模2的加法與減法是等價的。

域F上的多項式稱為不可約的，當且僅當f(x)不能表示為兩個多項式的積。不可約多項式也被稱為素多項式。

求最大公因式

如果c(x)能同時整除a(x)和b(x)，a(x)和b(x)的任何因式都是c(x)的因式，則稱c(x)為a(x)和b(x)的最大公因式
通過改寫歐幾里得算法可以計算兩個多項式的最大公因式
gcd[a(x)，b(x)]=gcd[b(x)，a(x) mod b(x)]。

有限域GF(2ⁿ)

動機

上面討論了n=1時的有限域GF（p）上的運算，但這里p必須取素數，假設我們構造一個圖像加密算法，需要在像素0~255這個范圍上運算，但256并不是一個素數，小于256的最大素數是251，所以要使用以251為模的運算，但這樣251-255就沒法表示出了，可以將251-255分成兩部分來表示，但會麻煩一些。
所以為了方便使用和提供效率，我們希望這個整數集中的數與給定的二進制位數所能表達的信息一一對應而不出現浪費。也就是希望整數集的范圍是從0到2ⁿ-1，正好對應一個n位的字。但直接以2ⁿ（n＞1）為模是不行的，這樣的整數集并不是一個域，即使我們只需要加密算法使用加法和乘法，以2ⁿ為模也存在問題。
我們需要借助多項式算術構造一個包含2ⁿ個元素的集合，其上定義了加法和乘法使之成為一個域。給集合的每一個元素賦值為0到2ⁿ-1之間的唯一整數。

多項式模運算

構造的多項式集合S包括以下定義：

①該運算遵循代數基本規則中的普通多項式運算規則及如下兩條限制。
②系數運算以p為模，即遵循有限域Z_p上的運算規則。
③如果乘法運算的結果是次數大于n-1的多項式，那么必須將其除以某個次數為n的不可約多項式m(x)并取余式。對于多項式f(x)，這個余數可表示為r(x)=f(x)
mod m(x)。

所以有限域GF(2ⁿ)中加法就是按位做異或運算，乘法則需要選擇一個不可約多項式，如果乘法運算的結果是次數大于n-1的多項式就除以這個不可約多項式取余式。

計算上的考慮

GF(2ⁿ)中的每個多項式
都可以表示成一個n位的二進制整數。

加法
多項式加法是將相應的系數分別相加，而對于Z₂上的多項式，加法就是異或運算。所以GF(2ⁿ)中的兩個多項式加法等同于按位異或運算。

乘法
以AES中有限域為例，不可約多項式m(x)=x⁸+x⁴+x³+x+1，如果兩個多項式相乘得到的結果是一個次數小于8的多項式，就不用繼續運算，如果大于等于8，就進行模m(x)的約化。
這種乘法可以拆分成多次按位移和按位異或的運算來進行。

使用生成元

定義：

階為q的有限域F的生成元是一個元素，記為 g , 該元素的前q-1個冪構成了F的所有非零元素，即域F的元素為0，g⁰，…，g^q-2。考慮由多項式f(x)定義的域F,如果F內的一個元素b滿足f(b)=0，則稱b為多項式的f(x)的根。最后，可以證明一個不可約多項式的根g是這個不可約多項式定義的有限域的生成元.

---

總結

以上是生活随笔為你收集整理的密码学中数论和有限域基本概念的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。