1. AES選擇了一個有逆元的固定多樣式a(x)，那麼它的逆元a-1(x)是怎麼算出來的
擴展的歐幾里得演算法
2. ECC 演算法簡介
與 RSA（Ron Rivest，Adi Shamir，Len Adleman 三位天才的名字）一樣，ECC（Elliptic Curves Cryptography，橢圓曲線加密）也屬於公開密鑰演算法。
一、從平行線談起
平行線，永不相交。沒有人懷疑把：）不過到了近代這個結論遭到了質疑。平行線會不會在很遠很遠的地方相交了？事實上沒有人見到過。所以「平行線，永不相交」只是假設（大家想想初中學習的平行公理，是沒有證明的）。
既然可以假設平行線永不相交，也可以假設平行線在很遠很遠的地方相交了。即平行線相交於無窮遠點P∞（請大家閉上眼睛，想像一下那個無窮遠點P∞，P∞是不是很虛幻，其實與其說數學鍛煉人的抽象能力，還不如說是鍛煉人的想像力）。
給個圖幫助理解一下：
直線上出現P∞點，所帶來的好處是所有的直線都相交了，且只有一個交點。這就把直線的平行與相交統一了。為與無窮遠點相區別把原來平面上的點叫做平常點。
以下是無窮遠點的幾個性質。
直線 L 上的無窮遠點只能有一個。（從定義可直接得出）
平面上一組相互平行的直線有公共的無窮遠點。（從定義可直接得出）
平面上任何相交的兩直線 L1、L2 有不同的無窮遠點。（否則 L1 和 L2 有公共的無窮遠點 P ，則 L1 和 L2 有兩個交點 A、P，故假設錯誤。）
平面上全體無窮遠點構成一條無窮遠直線。（自己想像一下這條直線吧）
平面上全體無窮遠點與全體平常點構成射影平面。
二、射影平面坐標系
射影平面坐標系是對普通平面直角坐標系（就是我們初中學到的那個笛卡兒平面直角坐標系）的擴展。我們知道普通平面直角坐標系沒有為無窮遠點設計坐標，不能表示無窮遠點。為了表示無窮遠點，產生了射影平面坐標系，當然射影平面坐標系同樣能很好的表示舊有的平常點（數學也是「向下兼容」的）。
我們對普通平面直角坐標繫上的點A的坐標（x, y）做如下改造：
令 x=X/Z ，y=Y/Z（Z≠0）；則 A 點可以表示為（X:Y:Z）。
變成了有三個參量的坐標點，這就對平面上的點建立了一個新的坐標體系。
例 2.1：求點（1,2）在新的坐標體系下的坐標。
解：
∵X/Z=1 ，Y/Z=2（Z≠0）
∴X=Z，Y=2Z
∴坐標為（Z:2Z:Z），Z≠0。
即（1:2:1）（2:4:2）（1.2:2.4:1.2）等形如（Z:2Z:Z），Z≠0 的坐標，都是（1,2）在新的坐標體系下的坐標。
我們也可以得到直線的方程 aX+bY+cZ=0（想想為什麼？提示：普通平面直角坐標系下直線一般方程是 ax+by+c=0）。
新的坐標體系能夠表示無窮遠點么？那要讓我們先想想無窮遠點在哪裡。根據上一節的知識，我們知道無窮遠點是兩條平行直線的交點。那麼，如何求兩條直線的交點坐標？這是初中的知識，就是將兩條直線對應的方程聯立求解。
平行直線的方程是：
aX+bY+c1Z =0；
aX+bY+c2Z =0 (c1≠c2)； （為什麼？提示：可以從斜率考慮，因為平行線斜率相同）；
將二方程聯立，求解。有
c2Z= c1Z= -（aX+bY）
∵c1≠c2
∴Z=0
∴aX+bY=0
所以無窮遠點就是這種形式（X：Y：0）表示。注意，平常點 Z≠0，無窮遠點 Z=0，因此無窮遠直線對應的方程是 Z=0。
例 2.2：求平行線 L1：X+2Y+3Z=0 與 L2：X+2Y+Z=0 相交的無窮遠點。
解：
因為 L1∥L2
所以有 Z=0， X+2Y=0
所以坐標為（-2Y:Y:0），Y≠0。
即（-2:1:0）（-4:2:0）（-2.4:1.2:0）等形如（-2Y:Y:0），Y≠0 的坐標，都表示這個無窮遠點。
看來這個新的坐標體系能夠表示射影平面上所有的點，我們就把這個能夠表示射影平面上所有點的坐標體系叫做射影平面坐標系。
練習：
1、求點A(2,4) 在射影平面坐標系下的坐標。
2、求射影平面坐標系下點(4.5:3:0.5)，在普通平面直角坐標系下的坐標。
3、求直線X+Y+Z=0上無窮遠點的坐標。
4、判斷：直線aX+bY+cZ=0上的無窮遠點 和 無窮遠直線與直線aX+bY=0的交點，是否是同一個點？
三、橢圓曲線
上一節，我們建立了射影平面坐標系，這一節我們將在這個坐標系下建立橢圓曲線方程。因為我們知道，坐標中的曲線是可以用方程來表示的（比如：單位圓方程是 x2+y2=1）。橢圓曲線是曲線，自然橢圓曲線也有方程。
橢圓曲線的定義：
一條橢圓曲線是在射影平面上滿足如下方程的所有點的集合，且曲線上的每個點都是非奇異（或光滑）的。
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3 [3-1]
定義詳解：
Y2Z+a1XYZ+a3YZ2 = X3+a2X2Z+a4XZ2+a6Z3 是 Weierstrass 方程（維爾斯特拉斯，Karl Theodor Wilhelm Weierstrass,1815-1897），是一個齊次方程。
橢圓曲線的形狀，並不是橢圓的。只是因為橢圓曲線的描述方程，類似於計算一個橢圓周長的方程（計算橢圓周長的方程，我沒有見過，而對橢圓線 積分 （設密度為1）是求不出來的），故得名。
我們來看看橢圓曲線是什麼樣的。
所謂「非奇異」或「光滑」的，在數學中是指曲線上任意一點的偏導數 Fx(x,y,z)，Fy(x,y,z)，Fz(x,y,z) 不能同時為0。如果你沒有學過高等數學，可以這樣理解這個詞，即滿足方程的任意一點都存在切線。下面兩個方程都不是橢圓曲線，盡管他們是方程 [3-1] 的形式，因為他們在（0:0:1）點處（即原點）沒有切線。
橢圓曲線上有一個無窮遠點O∞（0:1:0），因為這個點滿足方程[3-1]。
知道了橢圓曲線上的無窮遠點。我們就可以把橢圓曲線放到普通平面直角坐標繫上了。因為普通平面直角坐標系只比射影平面坐標系少無窮遠點。我們在普通平面直角坐標繫上，求出橢圓曲線上所有平常點組成的曲線方程，再加上無窮遠點O∞（0:1:0），不就構成橢圓曲線了么？
我們設 x=X/Z，y=Y/Z 代入方程 [3-1] 得到：
y2+a1xy+a3y = x3+a2x2+a4x+a6 [3-2]
也就是說滿足方程 [3-2] 的光滑曲線加上一個無窮遠點O∞，組成了橢圓曲線。為了方便運算，表述，以及理解，今後論述橢圓曲線將主要使用 [3-2] 的形式。
本節的最後，我們談一下求橢圓曲線一點的切線斜率問題。由橢圓曲線的定義可以知道，橢圓曲線是光滑的，所以橢圓曲線上的平常點都有切線。而切線最重要的一個參數就是斜率 k 。
例 3.1：求橢圓曲線方程 y2+a1xy+a3y=x3+a2x2+a4x+a6上，平常點 A(x,y) 的切線的斜率 k 。
解：
令
F(x,y)= y2+a1xy+a3y-x3-a2x2-a4x-a6
求偏導數
Fx(x,y)= a1y-3x2-2a2x-a4
Fy(x,y)= 2y+a1x+a3
則導數為：
f'(x)=- Fx(x,y)/ Fy(x,y)=-( a1y-3x2-2a2x-a4)/(2y+a1x +a3) = (3x2+2a2x+a4-a1y) /(2y+a1x +a3)
所以
k=(3x2+2a2x+a4-a1y) /(2y+a1x +a3) [3-3]
看不懂解題過程沒有關系，記住結論[3-3]就可以了。
練習：
1、將給出圖例的橢圓曲線方程Y2Z=X3-XZ2 和Y2Z=X3+XZ2+Z3轉換成普通平面直角坐標繫上的方程。
四、橢圓曲線上的加法
上一節，我們已經看到了橢圓曲線的圖象，但點與點之間好象沒有什麼聯系。我們能不能建立一個類似於在實數軸上加法的運演算法則呢？天才的數學家找到了這一運演算法則
自從近世紀代數學引入了群、環、域的概念，使得代數運算達到了高度的統一。比如數學家總結了普通加法的主要特徵，提出了加群（也叫交換群，或 Abel（阿貝爾）群），在加群的眼中。實數的加法和橢圓曲線的上的加法沒有什麼區別。這也許就是數學抽象把。關於群以及加群的具體概念請參考近世代數方面的數學書。
運演算法則：任意取橢圓曲線上兩點 P、Q （若 P、Q兩點重合，則做 P 點的切線）做直線交於橢圓曲線的另一點 R』，過 R』 做 y 軸的平行線交於 R。我們規定 P+Q=R。（如圖）
法則詳解：
這里的 + 不是實數中普通的加法，而是從普通加法中抽象出來的加法，他具備普通加法的一些性質，但具體的運演算法則顯然與普通加法不同。
根據這個法則，可以知道橢圓曲線無窮遠點 O∞ 與橢圓曲線上一點 P 的連線交於 P』，過 P』 作 y 軸的平行線交於 P，所以有 無窮遠點 O∞ + P = P 。這樣，無窮遠點 O∞ 的作用與普通加法中零的作用相當（0+2=2），我們把無窮遠點 O∞ 稱為零元。同時我們把 P』 稱為 P 的負元（簡稱，負P；記作，-P）。（參見下圖）
根據這個法則，可以得到如下結論 ：如果橢圓曲線上的三個點 A、B、C，處於同一條直線上，那麼他們的和等於零元，即 A+B+C= O∞
k 個相同的點 P 相加，我們記作 kP。如下圖：P+P+P = 2P+P = 3P。
下面，我們利用 P、Q點的坐標 (x1,y1)，(x2,y2)，求出 R=P+Q 的坐標 (x4,y4)。
例 4.1：求橢圓曲線方程 y2+a1xy+a3y=x3+a2x2+a4x+a6 上，平常點 P(x1,y1)，Q(x2,y2) 的和 R(x4,y4) 的坐標。
解：
（1）先求點 -R(x3,y3)
因為 P, Q, -R 三點共線，故設共線方程為
y=kx+b
其中，若 P≠Q (P,Q兩點不重合)，則直線斜率
k=(y1-y2)/(x1-x2)
若 P=Q (P,Q兩點重合)，則直線為橢圓曲線的切線，
故由例 3.1 可知：
k=(3x2+2a2x+a4 -a1y) /(2y+a1x+a3)
因此 P, Q, -R 三點的坐標值就是以下方程組的解：
y2+a1xy+a3y=x3+a2x2+a4x+a6 [1]
y=(kx+b) [2]
將 [2] 代入[1] 有
(kx+b)2+a1x(kx+b)+a3(kx+b) =x3+a2x2+a4x+a6 [3]
對 [3] 化為一般方程，根據三次方程根與系數關系（若方程x³＋ax²＋bx＋c=0 的三個根是 x1、x2、x3，則： x1＋x2＋x3=－a，x1x2＋x2x3＋x3x1=b，x1x2x2=－c）
所以
-(x1+x2+x3)=a2-ka1-k2
x3=k2+ka1+a2+x1+x2 --------------------- 求出點 -R 的橫坐標
因為
k=(y1-y3)/(x1-x3)
故
y3=y1-k(x1-x3) ------------------------------ 求出點 -R 的縱坐標
（2）利用 -R 求 R
顯然有
x4=x3=k2+ka1+a2+x1+x2 -------------- 求出點 R 的橫坐標
而 y3 y4 為 x=x4 時 方程 y2+a1xy+a3y=x3+a2x2+a4x+a6 的解化為一般方程 y2+(a1x+a3)y-(x3+a2x2+a4x+a6)=0 , 根據二次方程根與系數關系（如果方程 ax²＋bx＋c=0 的兩根為 x1、x2，那麼 x1+x2=-b/a，x1x2=c/a）
得：
-(a1x+a3)=y3+y4
故
y4=-y3-(a1x+a3)=k(x1-x4)-y1-(a1x4+a3) ----- 求出點 R 的縱坐標
即：
x4=k2+ka1+a2+x1+x2
y4=k(x1-x4)-y1-a1x4-a3
本節的最後，提醒大家注意一點，以前提供的圖像可能會給大家產生一種錯覺，即橢圓曲線是關於 x 軸對稱的。事實上，橢圓曲線並不一定關於 x 軸對稱。如下圖的 y2-xy=x3+1
五、密碼學中的橢圓曲線
我們現在基本上對橢圓曲線有了初步的認識，這是值得高興的。但請大家注意，前面學到的橢圓曲線是連續的，並不適合用於加密。所以，我們必須把橢圓曲線變成離散的點。
讓我們想一想，為什麼橢圓曲線為什麼連續？是因為橢圓曲線上點的坐標，是實數的（也就是說前面講到的橢圓曲線是定義在實數域上的），實數是連續的，導致了曲線的連續。因此，我們要把橢圓曲線定義在有限域上（顧名思義，有限域是一種只有由有限個元素組成的域）。
域的概念是從我們的有理數，實數的運算中抽象出來的，嚴格的定義請參考近世代數方面的數。簡單的說，域中的元素同有理數一樣，有自己得加法、乘法、除法、單位元(1)，零元(0),並滿足交換率、分配率。
下面，我們給出一個有限域 Fp，這個域只有有限個元素。
Fp 中只有 p（p為素數）個元素 0, 1, 2 …… p-2, p-1
Fp 的加法（a+b）法則是 a+b≡c (mod p) ，即 (a+c)÷p 的余數和 c÷p 的余數相同。
Fp 的乘法（a×b）法則是 a×b≡c (mod p)
Fp 的除法（a÷b）法則是 a/b≡c (mod p)，即 a×b-1≡c (mod p) ，b-1 也是一個 0 到 p-1 之間的整數，但滿足 b×b-1≡1 (mod p)；具體求法可以參考初等數論。
Fp 的單位元是 1，零元是 0。
同時，並不是所有的橢圓曲線都適合加密。y2=x3+ax+b是一類可以用來加密的橢圓曲線，也是最為簡單的一類。下面我們就把 y2=x3+ax+b 這條曲線定義在 Fp 上：
選擇兩個滿足下列條件的小於 p ( p 為素數) 的非負整數 a、b
4a3+27b2≠0 (mod p)
則滿足下列方程的所有點 (x,y)，再加上 無窮遠點 O∞ ，構成一條橢圓曲線。
y2=x3+ax+b (mod p)
其中 x,y 屬於 0 到 p-1 間的整數，並將這條橢圓曲線記為 Ep(a,b)。
我們看一下 y2=x3+x+1 (mod 23) 的圖像
是不是覺得不可思議？橢圓曲線，怎麼變成了這般模樣，成了一個一個離散的點？橢圓曲線在不同的數域中會呈現出不同的樣子，但其本質仍是一條橢圓曲線。舉一個不太恰當的例子，好比是水，在常溫下，是液體；到了零下，水就變成冰，成了固體；而溫度上升到一網路，水又變成了水蒸氣。但其本質仍是 H2O。
Fp上的橢圓曲線同樣有加法，但已經不能給以幾何意義的解釋。不過，加法法則和實數域上的差不多，請讀者自行對比。
1. 無窮遠點 O∞ 是零元，有 O∞ + O∞ = O∞，O∞ + P = P
2. P(x,y) 的負元是 (x,-y)，有 P + (-P) = O∞
3. P(x1,y1), Q(x2,y2) 的和 R(x3,y3) 有如下關系：
x3≡k2-x1-x2(mod p)
y3≡k(x1-x3)-y1(mod p)
其中
若 P=Q 則 k=(3x2+a)/2y1
若 P≠Q 則 k=(y2-y1)/(x2-x1)
例 5.1：已知 E23(1,1) 上兩點 P(3,10)，Q(9,7)，求 (1)-P，(2)P+Q，(3) 2P。
解：
(1) –P的值為(3,-10)
(2) k=(7-10)/(9-3)=-1/2
2 的乘法逆元為 12， 因為 2*12≡1 (mod 23)
k≡-1*12 (mod 23)
故 k=11
x=112-3-9=109≡17 (mod 23)
y=11[3-(-6)]-10=89≡20 (mod 23)
故 P+Q 的坐標為 (17,20)
3) k=[3(32)+1]/(2*10)=1/4≡6 (mod 23)
x=62-3-3=30≡20 (mod 23)
y=6(3-7)-10=-34≡12 (mod 23)
故 2P 的坐標為 (7,12)
最後，我們講一下橢圓曲線上的點的階。如果橢圓曲線上一點 P，存在最小的正整數 n，使得數乘 nP=O∞，則將 n 稱為 P 的階，若 n 不存在，我們說 P 是無限階的。 事實上，在有限域上定義的橢圓曲線上所有的點的階 n 都是存在的（證明，請參考近世代數方面的書）
練習：
1． 求出 E11(1,6) 上所有的點。
2．已知 E11(1,6) 上一點 G(2,7)，求 2G 到 13G 所有的值。
六、橢圓曲線上簡單的加密/解密
公開密鑰演算法總是要基於一個數學上的難題。比如 RSA 依據的是：給定兩個素數 p、q 很容易相乘得到 n，而對 n 進行因式分解卻相對困難。那橢圓曲線上有什麼難題呢？
考慮如下等式：
K=kG [其中 K, G為 Ep(a,b) 上的點，k 為小於 n（n 是點 G 的階）的整數]
不難發現，給定 k 和 G，根據加法法則，計算 K 很容易；但給定 K 和 G，求 k 就相對困難了。這就是橢圓曲線加密演算法採用的難題。我們把點 G 稱為基點（base point），k（key point）就是私有密鑰。
現在我們描述一個利用橢圓曲線進行加密通信的過程：
1、用戶 A 選定一條橢圓曲線 Ep(a,b)，並取橢圓曲線上一點，作為基點 G。
2、用戶 A 選擇一個私有密鑰 k，並生成公開密鑰 K=kG。
3、用戶 A 將 Ep(a,b) 和點 K，G 傳給用戶 B。
4、用戶 B 接到信息後，將待傳輸的明文編碼到 Ep(a,b) 上一點 M（編碼方法很多，這里不作討論），並產生一個隨機整數 r（random）。
5、用戶 B 計算點 C1=M+rK；C2=rG。
6、用戶 B 將 C1、C2 傳給用戶A。
7、用戶 A 接到信息後，計算 C1-kC2，結果就是點 M。因為 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M ，再對點 M 進行解碼就可以得到明文。
在這個加密通信中，如果有一個偷窺者 H ，他只能看到 Ep(a,b)、K、G、C1、C2 而通過 K、G 求 k 或通過 C2、G 求 r 都是相對困難的。因此，H 無法得到 A、B 間傳送的明文信息。
密碼學中，描述一條 Fp 上的橢圓曲線，常用到六個參量：
T=(p,a,b,G,n,h)
p 、a 、b 用來確定一條橢圓曲線，G 為基點，n 為點 G 的階，h 是橢圓曲線上所有點的個數 m 與 n 相除的整數部分。這幾個參量取值的選擇，直接影響了加密的安全性。參量值一般要求滿足以下幾個條件：
1、p 當然越大越安全，但越大，計算速度會變慢，200 位左右可以滿足一般安全要求；
2、p≠n×h；
3、pt≠1 (mod n)，1≤t<20；
4、4a3+27b2≠0 (mod p)；
5、n 為素數；
6、h≤4。
七、橢圓曲線簽名在軟體保護的應用
我們知道將公開密鑰演算法作為軟體注冊演算法的好處是：黑客很難通過跟蹤驗證演算法得到注冊機。下面，將簡介一種利用 Fp(a,b) 橢圓曲線進行軟體注冊的方法。
軟體作者按如下方法製作注冊機（也可稱為簽名過程）
1、選擇一條橢圓曲線 Ep(a,b) 和基點 G；
2、選擇私有密鑰 k；
3、產生一個隨機整數 r ；
4、將用戶名和點 R 的坐標值 x,y 作為參數，計算 SHA（Secure Hash Algorithm 安全散列演算法，類似於 MD5）值，即 Hash=SHA(username,x,y)；
5、計算 sn≡r - Hash * k (mod n)
6、將 sn 和 Hash 作為用戶名 username 的序列號
軟體驗證過程如下：（軟體中存有橢圓曲線 Ep(a,b) 和基點 G 以及公開密鑰 K）
1、從用戶輸入的序列號中，提取 sn 以及 Hash；
2、計算點 R≡sn*G+Hash*K ( mod p )，如果 sn、Hash 正確，其值等於軟體作者簽名過程中點 R(x,y) 的坐標，
因為 sn≡r-Hash*k （mod n）
所以 sn*G+Hash*K=(r-Hash*k)*G+Hash*K=rG-Hash*kG+Hash*K=rG-Hash*K+Hash*K=rG=R；
3、將用戶名和點 R 的坐標值 x,y 作為參數，計算 H=SHA(username,x,y)；
4、如果 H=Hash 則注冊成功，如果 H≠Hash ，則注冊失敗（為什麼？提示注意點 R 與 Hash 的關聯性）。
簡單對比一下兩個過程：
作者簽名用到了：橢圓曲線 Ep(a,b)，基點 G，私有密鑰 k，及隨機數 r。
軟體驗證用到了：橢圓曲線 Ep(a,b)，基點 G，公開密鑰 K。
黑客要想製作注冊機，只能通過軟體中的 Ep(a,b)，點 G，公開密鑰 K ，並利用 K=kG 這個關系獲得 k 才可以，而求 k 是很困難的。
練習：
下面也是一種常於軟體保護的注冊演算法，請認真閱讀，並試回答簽名過程與驗證過程都用到了那些參數，黑客想製作注冊機，應該如何做。
軟體作者按如下方法製作注冊機（也可稱為簽名過程）
1、選擇一條橢圓曲線 Ep(a,b)，和基點 G；
2、選擇私有密鑰 k；
3、產生一個隨機整數 r；
4、將用戶名作為參數，計算 Hash=SHA(username)；
5、計算 x』=x (mod n)
6、計算 sn≡(Hash+x』*k)/r (mod n)
7、將 sn 和 x』 作為用戶名 username 的序列號
軟體驗證過程如下：(軟體中存有橢圓曲線 Ep(a,b) 和基點 G 以及公開密鑰 K)
1、從用戶輸入的序列號中，提取 sn 以及 x』；
2、將用戶名作為參數，計算 Hash=SHA(username)；
3、計算 R=(Hash*G+x』*K)/sn，如果 sn、Hash 正確，其值等於軟體作者簽名過程中點 R(x,y)
因為 sn≡(Hash+x』*k)/r (mod n)
所以 (Hash*G+x』*K)/sn=(Hash*G+x』*K)/[(Hash+x』*k)/r]=(Hash*G+x』*K)/[(Hash*G+x』*k*G)/(rG)]=rG*[(Hash*G+x』*K)/(Hash*G+x』*K)]=rG=R (mod p)
4、v≡x (mod n)
5、如果 v=x』 則注冊成功。如果 v≠x』 ，則注冊失敗。
主要參考文獻
張禾瑞，《近世代數基礎》，高等 教育 出版社，1978
閔嗣鶴 嚴士健，《初等數論》，高等教育出版社，1982
段雲所，《網路信息安全》第三講，北大計算機系
Michael Rosing ，chapter5《Implementing Elliptic Curve Cryptography》，Softbound，1998
《SEC 1: Elliptic Curve Cryptography》，Certicom Corp.，2000
《IEEE P1363a / D9》，2001
3. 用擴展歐幾里得（Euclid）演算法計算1234 mod 4321的乘法逆元
Q X1 X2 X3 Y1 Y2 Y3
1 0 4321 0 1 1234
3 0 1 1234 1 -3 619
1 1 -3 619 -1 4 615
1 -1 4 615 2 -7 4
153 2 -7 4 -307 1075 3
1 -307 1075 2 309 -1082 1
4321-1082=3239
4. 最大公約數怎麼求演算法
求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法。
1、質因數分解法
把每個數分別分解質因數，再把各數中的全部公有質因數提取出來連乘，所得的積就是這幾個數的最大公約數。
例如：求24和60的最大公約數，先分解質因數，得24=2×2×2×3，60=2×2×3×5，24與60的全部公有的質因數是2、2、3，它們的積是2×2×3=12，所以，（24，60）＝12。
2、短除法
短除法求最大公約數，先用這幾個數的公約數連續去除，一直除到所有的商互質為止，然後把所有的除數連乘起來，所得的積就是這幾個數的最大公約數。
3、輾轉相除法
輾轉相除法也叫歐幾里德演算法。用輾轉相除法求幾個數的最大公約數，可以先求出其中任意兩個數的最大公約數，再求這個最大公約數與第三個數的最大公約數，依次求下去，直到最後一個數為止。最後所得的那個最大公約數，就是所有這些數的最大公約數。
4、更相減損法
也叫更相減損術，是出自《九章算術》的一種求最大公約數的演算法，它原本是為約分而設計的，但它適用於任何需要求最大公約數的場合。
《九章算術》是中國古代的數學專著，其中的「更相減損術」可以用來求兩個數的最大公約數，即「可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。」
翻譯成現代語言如下：
第一步：任意給定兩個正整數；判斷它們是否都是偶數。若是，則用2約簡；若不是則執行第二步。
第二步：以較大的數減較小的數，接著把所得的差與較小的數比較，並以大數減小數。繼續這個操作，直到所得的減數和差相等為止。
則第一步中約掉的若干個2與第二步中等數的乘積就是所求的最大公約數。
其中所說的「等數」，就是最大公約數。求「等數」的辦法是「更相減損」法。所以更相減損法也叫等值演算法。
擴展歐幾里德演算法
擴展歐幾里得演算法（又稱擴充歐幾里得演算法）是用來解某一類特定的不定方程的一種方法，常用用來求解模線性方程及方程組。擴展的歐幾里得演算法可以用來計算模逆元，而模逆元在公鑰密碼學中佔有舉足輕重的地位。
基本演算法：對於不完全為 0 的非負整數 a，b，gcd（a，b）表示 a，b 的最大公約數，必然存在整數對 x，y ，使得 gcd（a，b）=ax+by。
5. 請問在密碼學中如何求乘法逆元素（最好有詳細演算法）
這個敘述起來比較麻煩，你要演算法的話比較長，你可以查詢廣義歐幾里得法，現在很多開發工具和編程語言都有的，人家直接寫好了在有限域內求乘法擬元的方法的，是在不行，你根據定義做窮舉檢索也總能找到逆元的！
6. 擴展歐幾里得演算法求乘法逆元1234
Q X1 X2 X3 Y1 Y2 Y31 0 4321 0 1 12343 0 1 1234 1 -3 6191 1 -3 619 -1 4 6151 -1 4 615 2 -7 4153 2 -7 4 -307 1075 31 -307 1075 2 309 -1082 14321-1082=3239
7. 密碼學基礎2：橢圓曲線密碼學原理分析
首先要說明的一點是，橢圓曲線不是橢圓。橢圓方程是下面這樣的：
而通常我們討論的橢圓曲線的曲線方程是一個二元三次方程，它有多種形式，在橢圓曲線密碼體系中，最常用的是如下的Weierstrass通用式(curve25519 等其他類型的橢圓曲線本文不討論)：
之所以取名叫橢圓曲線，是因為該曲線方程跟求橢圓弧長的積分公式相似。從曲線方程和圖像易知，橢圓曲線關於X軸對稱。判定式不等於零是為了橢圓曲線不存在奇異點，即處處光滑可導，這樣才能進行橢圓曲線上的加法運算。下面是一些適合用於加密的橢圓曲線，其中 。
橢圓曲線加密演算法涉及數學中的群論、有限域等內容，這節簡要介紹下相關數學理論。亦可以跳過直接看第3節，遇到相關名詞再查閱即可。
在討論群之前，先說說集合。集合簡單來說就是把一堆東西放在一起，如自然數集合。當然光有一堆東西還不夠，東西之間相互作用才能更好的描述大千世界。於是，自然數集合通過加減運算衍生出整數集合、整數集合經過乘除又可以衍生出有理數，而後通過無理數的加入又衍生出實數集合、負數開方引入了復數集合。群則是集合和一個二元運算。
而如果再滿足交換律，則該群就被稱為是一個阿貝爾群。
根據群的定義，整數的加法運算 就是一個群，而且還是一個阿貝爾群。而自然數的加法運算 就不是一個群。整數加法運算構成群，因為它滿足群的定義：整數加法的封閉性、結合律、交換律都成立。整數加法運算中單位元是 0。所有整數 n 都有加法逆元 -n。
在密碼學中一般都需要一個有限的群，定義如下:
為了使一個結構同時支持四種基本算術(即加減乘除)，我們需要一個包含加法和乘法群的集合，這就是域。當一個集合為域的時候，我們就能在其中進行基本算術運算了。
所以域中元素只要形成加法群和乘法群並滿足分配律就行，因為群中元素都有逆元，減法/除法可以轉換為加/乘元素的逆元實現。實數集合 是一個域，加法群中單位元是 0，每個實數 都有加法逆元 ，乘法群中單位元是 ，每個非零實數都有乘法逆元 。而整數集合就不是域，因為大部分元素沒有乘法逆元，不能構成一個乘法群。
在密碼學中，通常只對有限元素的域感興趣，這種域稱為有限域(Finite Field)。有限域中我們經常用到的是素數域，所謂素數域，就是階為素數的有限域。 比如當 p 為素數時，整數環 就是一個素數域，可以記作 。在素數域 中進行算術運算，需要遵守整數環的規則，即加法是模 p 加法，而乘法是模 p 乘法。
例如對於 有：
橢圓曲線上的點經過一種特定的加法運算可以讓橢圓曲線在實數域構成一個群。
無窮遠點 ：定義一個無窮遠點 ，即經過橢圓上任意一點的與X軸垂直的直線都經過該點。可能有人疑惑垂直於X軸的直線是平行線，為啥可以定義為都經過 點？因為在非歐幾何中，可認為平行線在無窮遠處會交於一點。
橢圓曲線點加法 ：橢圓曲線上經過 和 兩個點的直線與橢圓曲線的交點記作 ，根據定義有 以及 。繼而定義橢圓曲線點加法： ，即加法結果是經過點 且與 X 軸垂直的直線與橢圓曲線的另外一個交點，簡單來說，就是交點 關於 X 軸的對稱點。
橢圓曲線群：定義為橢圓曲線在實數域上的點集以及點加法
由此可知，橢圓曲線上的點在橢圓曲線加法運算上構成了一個阿貝爾群。增加了單位元後，橢圓曲線方程改為：
由定義可知， ，所以，最終加法只需要計算交點 的逆元 即可。 幾種特殊情況說明：
上一節定義了橢圓曲線幾何上意義的點加法，需要轉換為代數加法以方便計算。 要注意的是，這並不是兩個點的坐標簡單相加 。
假設直線 PQ 的斜率 ，然後將直線方程 代入曲線可以得到： , 轉換成標準式，根據韋達定理 ，即而可求得 ，想了解具體推導過程的可參見 [cubic-equations] 。
斜率 計算需要區分兩種情況，當 P=Q 時求橢圓曲線在 P 點的切線斜率(求導)即可：
可以簡單驗證，比如橢圓曲線是 ，通過參考資料1的 [可視化工具] 可得 。容易驗證，與代數加法公式計算結果一致。
對於特殊情況 中有一個是切點的情況，如 ，計算方式不變，易得 。而對於特殊情況 ，採用切線斜率亦可驗證公式正確。
在實際加密演算法中，我們通常需要多次通過橢圓曲線加法來實現一次加密，如下圖所示：
圖中打點的過程就是：
而在實際加密演算法中，我們常常是使用一個點自己疊加，即初始直線變成橢圓曲線的切線即可，像下面這樣：
我們定義對一個點 P 進行 n 次加法得到 nP，稱之為標量乘法。如前面例子中 。
不過，當 n 很大時，執行 n 次加法需要 時間，效率有問題。 因為橢圓曲線點加法在實數域構成阿貝爾群，滿足交換律和結合律，於是可以通過 [Double-and-add] 演算法進行優化 。比如 ，其二進製表示為 ，通過優化只要7次倍乘和4次加法計算即可，時間復雜度降到 。這是一個很好的單向函數，正向計算容易，而反向和蠻力計算復雜。
令 ，則 Q 作為公鑰，n 為私鑰。如果要破解該密鑰，問題就是 "Q = nP，如果已知 P 和 Q，如何求解 n"? 這個問題是比較困難的。不過由於在實數域上曲線連續，可能會更容易找到一些規律進行破解。而且實數域上數值大小沒有限制、浮點數等問題而導致計算效率問題，在實際應用中常將橢圓曲線限制到一個有限域內，將曲線變成離散的點，這樣即方便了計算也加大了破解難度。
前面提到為了安全性和便於實現，需要將橢圓曲線限制到一個有限域內，通常用的是素數域 (即對於點 為素數)。於是破解就會變成一個離散對數問題，這比連續曲線上的對數問題會難很多。素數域下橢圓曲線定義如下：
下面是曲線 和 的圖像。可以發現，橢圓曲線變成了離散的點，且關於 對稱。
定義 上橢圓曲線點加法 如下，公式跟實數域上相比只是多了模 操作。
斜率 m 計算同樣分兩種情況：
橢圓曲線在素數域 上的點加法依然構成阿貝爾群。單位元依舊是無窮遠點，元素 的逆元變成 。而交換律、結合律、封閉性則可以通過素域上的模加法、模乘法來證明 。實數域的橢圓曲線點加法定義是有明確幾何意義的，從幾何上好證明。而橢圓曲線在 就沒有明顯的幾何意義了，觀察可發現 三點滿足 ，群律的證明過於繁瑣，略去(其實是沒有找到一個簡易的證明)。
以前面曲線為例， ，則有 ，且 和 都在橢圓曲線上。從圖形上看， 在直線 上。
在有限域下，橢圓曲線加法群的元素是有限的，元素數目就是群的階。
如橢圓曲線 ，其在素數域 中元素有 ，階為24(23個素數域中的點 + 1個無窮遠點)，如果 p 很大的話，則通過蠻力計算階是很難的，好在使用 [Schoof演算法] 可以在多項式時間內計算出群的階。計算橢圓曲線在有限域上點的數目可以參見 [Counting points on elliptic curves] 。
Schoof演算法運用了 Hasses 定理。Hasses定理給出了橢圓曲線在 的階的范圍，可以看出，當 p 很大時，階跟 p 的值是比較接近的。
跟實數域一樣，在素數域裡面也是選取一個點 P，然後計算倍乘 nP 作為公鑰。還是以 為例， ，我們採用素數域下新的計算公式計算 。
可以發現 ，即 P 的標量乘法得到的點集是原橢圓曲線群的一個子集，則它是原橢圓曲線群的一個子群，而且是循環子群。子群中元素個數稱為子群的階(示例子群的階為8)，點 P 稱為該子群的基點或者生成元。循環子群是橢圓曲線密碼體系的基礎，我們期望子群中元素越多越好，如何找到一個合適的子群尤為重要。
首先要解決一個問題，就是已知 下的橢圓曲線上的點 P，如何求得 P 的倍乘運算後生成的子群的階? 根據拉格朗日的群論定理，子群的階是父群的階的約數。求解曲線上點 P 生成的子群的階可以用下面方法：
以示例曲線為例，父群的階是 ，則以曲線上的點生成的子群的階只能是 。對於點 ，故其生成的子群的階就是 8，而點 生成的子群的階則正好等於父群的階24。
在加密演算法中，我們期望找到一個階高的子群。不過，通常不是先去找個基點，然後計運算元群的階，因為這樣過於不確定，演算法上不好實現。相反地，先選擇一個大的子群階，然後再找生成該子群的一個基點就容易多了。
前面提到，子群的階 n 是父群的階 N 的約數，即有 ，h 是一個整數，我們稱之為子群的余因子(cofactor)。因為 ，所以有:
通常會選擇一個素數作為子群的階，即 n 是素數。可以發現，點 生成了階為 n 的子群( 除外，因為這個子群的階為1)，不等於 的點 就是我們尋找的基點。具體步驟如下：
需要注意，上面演算法里的 n 必須是素數，否則計算的基點 G 生成的子群的階可能是 n 的約數而不是 n，不符合要求 。以曲線 為例， ，我們選擇 ，則 ，隨機選取一個點 ，計算 ，恰好滿足要求。
如前所述，橢圓曲線加密演算法工作在素數域下的橢圓曲線循環子群中，需要的域參數(Domain Parameter)包括 ：
如比特幣用來做數字簽名中採用的橢圓曲線 [secp256k1] 的域參數如下：
8. 密碼學裡面的逆元是什麼意思啊
設<G,·>是一個幺半群，e是G的單位元，x∈G，若存在x'∈G，使得： 1. x'·x = e，則稱x'是x的左逆元。 2. x·x' = e，則稱x'是x的右逆元。 3. 若x'既是x的左逆元，又是x的右逆元，則x'稱為x的逆元。 注意： 1.G中元素的左逆元和右逆元不一定相等。 2.G中元素不一定都存在逆元。
編輯本段密碼學中的逆元
在模運算中， 加法單位元是0，因為(0+a) mod m = a mod m； 乘法單位元是1，因為(1×a) mod m = a mod m 定義 對a∈Zm，存在b∈Zm，使得a+b ≡ 0 (mod m)，則b是a的加法逆元，記b= - a。 定義 對a∈Zm，存在b∈Zm，使得a×b ≡1 (mod m)，則稱b為a的乘法逆元。 逆元在密碼學中有廣泛應用，AES密碼體系的位元組替代就是運用了逆元。
9. 密碼學+逆元+模加法群+模乘法群 的三道題。
8.因為(9+12)mod 21=0 ，所以(-9)=12
9.因為5*3 mod7=1 所以(5^(-1))=7
10.相當於求同餘式73x==1(mod 1001)的解，相當於解不定方程1001y=73x-1。先解同餘方程
1001y==(-1)(mod 73)，也就是解同餘方程52y==(-1)(mod 73) 52y+1=73z 73z==1(mod52)即21z==1(mod 52) 再設52w=21z-1求52w==-1(mod21)即10w==-1(mod21)，顯然w=2，逐級帶回，有z=5，y=7,x=96。所以73*96==1(mod 1001)，73逆元為96