群
群G，有時記為{G, . },是定義了一個二元運算的集合，這個二元運算可表示為 . ,G中的每一個序偶(a,b)通過運算生成G中的元素(a.b)，并滿足以下公理：
（A1）封閉性：如果a和b都屬于G，則a.b也屬于G。
（A2）結(jié)合律：對于G中任意a，b，c，都有(a.b).c=a.(b.c)成立。
（A3）單位元：G中存在一個元素e，對于G中任意元素a，都有a.e=e.a=a。
（A4）逆元：對于G中任意元素a，G中都存在一個元素a'，使得下式成立：a.a'=a'.a=e
如果一個群的元素是有限的，則該群稱為有限群，并且群的階就等于群中元素的個數(shù)。否則，稱該群為無限群。
一個群如果還滿足以下條件，則稱為交換群：
（A5）交換律：對于G中任意的元素a，b，都有a.b=b.a成立。
循環(huán)群
我們在群中定義求冪運算為重復(fù)運用群中的運算，如a3=a.a.a。而且，我們定義a0=e作為單位元；并且a-n=(a')n,其中a'是a在群內(nèi)的逆元算。如果群G中的每一個元素都是一個固定元素a(a屬于G)的冪ak(k為整數(shù))，則稱群G是循環(huán)群。我們認(rèn)為元素a生成了群G，或者說a是群G的生成元。循環(huán)群總是交換群，它可能是有限群或無限群。
在GF(p)中求乘法逆元
當(dāng)p值較小時，求GF(p)中元素的乘法逆元很容易。你只需構(gòu)造一個乘法表，所要的結(jié)果可以從中直接讀出。但是，當(dāng)p值比較大時，這種方法是不切實際的。
如果a和b互素，則b有模a的乘法逆元。也就是說，如果gcd(a,b)=1，那么b有模a的乘法逆元。即對于正整數(shù)b<a，存在b-1<a使bb-1=1 mod a。如果a是素數(shù)并且b<a,則顯然a和b互素，且其最大公因子為1。運用擴展的Euclid算法容易計算b-1
求乘法逆元
正如Euclid算法可以用來求兩個多項式的最大公因式，擴展Euclid算法則可以用來求一個多項式的乘法逆元。如果多項式b(x)的次數(shù)小于a(x)的次數(shù)
且gcd[a(x),b(x)]=1，那么該算法能求出b(x)以a(x)為模的乘法逆元。若a(x)為既約多項式，即除了本身與1之外沒有其他因式，則始終有g(shù)cd[a(x),b(x)]=1.
算法的描述方式和整數(shù)情形的擴展Euclid算法一樣。給定兩個多項式a(x)和b(x)，其中a(x)的次數(shù)大于b(x)的次數(shù)。我們希望解如下方程獲得v(x),w(x)以及d(x),其中d(x)=gcd[a(x),b(x)] : a(x)v(x)+b(x)w(x)=d(x)
如果d(x)=1,則w(x)是b(x)模a(x)的乘法逆元。
乘法逆元的應(yīng)用
滿足 a * k ≡ 1 (mod p) 的k 叫做 a關(guān)于p的乘法逆元。
另一種表達方法是 k ≡ a-1 (mod p)
逆元在密碼學(xué)中有廣泛應(yīng)用，AES密碼體系的字節(jié)替代就是運用了逆元。
應(yīng)用：
我們知道(a+b)%p=(a%p+b%p)%p
(ab)%p=(a%p)(b%p)%p
而求(a/b)%p時，可能會因為a是一個很大的數(shù)，不能直接算出來，卻又不能(a/b)%p=(a%p/b%p)%p。
但是可以通過 k ≡ b-1 (mod p)
應(yīng)用
a / b
= a * b-1 (mod p )
= (a mod p ) * (b-1 mod p ) mod p
= (a mod p ) * (k mod p ) mod p
= a * k mod p
轉(zhuǎn)換為a*k % p 的問題，然后a是一個加減乘的式子，就可以用上面兩個取余公式了
