1、羣環域

1.羣

羣G，記做{G，•}，定義一個二元運算•的集合，G中每個序偶（a，b）經過運算生成G中的元素（a•b），知足如下公理：算法

• 封閉性：若是a，b都屬於G，則a•b也屬於G
• 結合律：對於任意的a，b，c，都有a•(b•c)=(a•b)•c成立
• 單位元：G中存在一個元素e，對於G中任意元素a都有a•e = e•a = a
• 逆元：對於G中任意元素a，都存在a'∈G，使得a•a‘ = e

有限羣：若是一個羣中的元素是有限的則稱該羣爲有限羣，元素的個數即爲該羣的階數spa

無限羣：若是一個羣中的元素個數是無限的，則稱該羣爲無限羣code

交換羣（阿貝爾羣）: 若是對於羣中的任意兩個元素a，b都有a•b = b•a，則該羣爲交換羣blog

循環羣：若是羣中的每個元素都是一個固定元素a的冪a^n，n爲整數，則稱G爲循環羣，a是qunG的生成元ci

2.環

環R，記做{R，+，x}，是具備加法和乘法兩個二元運算的元素的集合，對於環中全部的a，b，c，都知足如下公理：it

• 對於加法知足羣的全部性質，且單位元是0，a的逆是-a
• 乘法封閉性：若a，b均屬於R，則ab屬於R
• 乘法結合律：對於R中任意的a，b，c，均知足a（bc） = （ab）c
• 分配律：a（b+c） = ab+ac,或者 (a+b)c = ac+bc

又有class

• 乘法交換律：ab=ba,知足乘法交換律的環是交換環
• 單位元：R中存在元素1使得a1=1a=a
• 無零因子：若R中有ab=0，則a=0或b=0

知足單位元和無零因子的交換環是整環cli

3.域

域F，記做{F，+，x}是具備加法和乘法兩個二元運算的集合，對於F中全部的a，b，c均有擴展

• 知足環的全部條件，即F是個整環
• 乘法逆元：對於F中任意元素a除0外，均有一個∈F使得a=a=1
• 域就是一個集合，定義減法爲a-b=a+b'即a+（-b），定義除法爲b/a=bx，在域上進行加減乘除運算結果都不脫離該集合

有理數集合，實數集合和複數集合都是域，整數集合不是域循環

4.羣環域的關係

2、同餘

若是a能整除b，則稱b是a的一個因子，記做b|a，有以下性質

• 若是a|1，則a=±1
• 若是a|b且b|a，則a=±b
• 任何b≠0，b都能整除0
• 若是b|g，b|h，則對任意整數m，n都有b|（mg+nh）
• 若是a≡0mod n，則n|a

給定整數a，b及n≠0，當且僅當a-b=kn時，a與b在模n時同餘，記做a≡b mod n 或者a≡ 

若是n|(a-b), 則a≡b mod n ,證實：

• 若是n|(a-b),則有a-b=kn
• 則a=b+kn
• a mod n = (b+kn)mod n
• a mod n = b mod n

a≡b mod n 且b≡c mod n 則a≡c mod n

模算數運算

• 反身性：a=a mod n
• 對稱性：若a=b mod n，則b=a mod n
• 傳遞性: 若a=b mod n 且b=c mod n，則a=c mod n
• 若是 a=b mod n且 c=d mod n，則

1. a+c=(b+d) mod n
2. a-c=(b-d) mod n
3. a•c=(b•d) mod n

(a1 op a2) mod n =[(a1 mod n )] op (a2 mod n)] mod n，即

• (a+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 • b mod n) mod n

3、歐幾里得算法Euclid Algorithm

對於任何非負的整數a和n，gcd(a, n)=gcd(n mod a, a)

假設咱們有整數a,b使得d=gcd(a,b)。假設a≥b>0，如今用b

除a，由除法可獲得

a=q1b+r1    0≤r1<b

若是恰巧r1=0，則b|a且d=gcd(a,b)=b。可是若是r1≠0,咱們

說d|r1。這基於除法的基本性質：由d|a和d|b能夠推出d|(a-

q1b)，即d|r1。如今假設有任意的整數c整除b和r1.所以

c|(q1b+r1)=a。所以c同時整除a和b，必須有c≤d，而d是a和

b的最大公因子。所以d=gcd(b,r1)

拓展的歐幾里得算法

對於給定的整數a和b，擴展的Euclid算法不只計算出最大公因子d，並且還有另外的整數x和y，它們知足以下方程：

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

 用擴展的Euclid算法計算(x,y,d).

假設在每一步驟i均可以找到xi和yi知足ri=axi+byi 

4、有限域

有限域在密碼學中扮演重要角色

有限域的階（元素個數），必須是一個素數的冪,記做GF（）

階爲p的有限域GF（p）

 給定a∈[0, n-1], gcd (a, n)=1，若能找到惟一整數x∈[0,n-1]，知足：ax mod n=1, 則稱a和x互逆

• 給定一個素數p，元素個數爲p的有限域GF(p)被定義爲整數{0,1, … , p-1}的集合Zp，其運算爲模p的算術運算
• Zn中的任一整數有乘法逆元當且僅當該整數與n互素，若n爲素數， Zn中的全部非零整數都與n互素，所以Zn中全部非零整數都有乘法逆元
• 對每個w∈Zp，存在一個z，使得w×z≡1 mod p，則z即爲乘法逆元
• 由於w與p互素，若是用w乘以Zp中的全部數模p，獲得的餘數將以不一樣次序涵蓋Zp中的全部數，即餘數集合是{0,1, … , p-1}的置換形，那麼至少有一個餘數的值爲1。所以，在Zp中的某個數與w相乘模p的餘數爲1, 這個數就是w的乘法逆元，。 因此，Zp是一個有限域

  如 n=10, a=3, x=7, ax mod n=1 =3x7 mod 10

若是gcd (a, n)=1, 則對於每一個i, j, 0≤i<j<n,

  ai mod n≠aj mod n

若是存在gcd（a，n）=1 ，則必定存在整數x在0到n之間知足ax mod n = 1

拓展的歐幾里得算法求逆

若是a，b互素，則b有模a的乘法逆元，也就是說，若是gcd（a，b）=1，對於正整數b<a，存在<a,使得b =1 mod a，若是a 是素數而且b < a，則顯然a,b互素，且最大公因子爲1

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

若是gcd(a, b)=1,則有ax+by=1.

[(ax mod a)+(by mod a)]mod a = 1 mod a

0+(by mod a)=1

若是by mod a=1，則y=

5、多項式計算

三種多項式計算

• 使用代數基本規則的普通多項式運算
• 係數運算是模p運算的多項式運算，即係數在GF(p)中
• 係數在GF(p)中，且多項式被定義爲模一個n次多項式m(x)的多項式運算

在此咱們只關心第三種

多項式能夠寫成以下形式

f(x) = q(x) g(x) + r(x)

其中，r(x)就可被看做是餘數r(x) = f(x) mod g(x)

• 若是沒有餘數，就稱g(x)能夠整除f(x)
• 若是g(x)除了1和它自身之外沒有其餘公因式，就稱它是不可約多項式或素多項式irreducible or prime