1、2 題 不確定是否完整,
就是第二個部份的證明不知道要不要寫,
如果需要就要再補上去,
不確定是否有打錯或是筆記操錯的地方有錯請指正,thanks
1. 寫出並證明費碼定理
Fermat 定理 ,當 (a,p)=1 (a跟p互質)
ap-1 = 1 mod p
證明:在Zp 之中 a、p互質
[1*2*3..*(p-1)]modp={(1*a)(
={a(p-1)*[1*2*3..*(p-1)]}modp <-右邊將a提出成為a的p-1次方
因為 a、p互質所以存在反元素將兩邊同乘反元素 [1*2*3..*(p-1)]-1 消掉
所以 1modp = a(p-1)modp -> ap-1 = 1 mod p
2. 寫出並證明尤拉定理
尤拉定理 ,當 (a,p)=1 (a跟p互質)
aΦ(n)=1 mod n
[X1*X2*X3..XΦ(n)]mod n =[(X1modn)(X2modn)(X3modn)…[XΦ(n)]modn] modn
[(X1modn)(X2modn)(X3modn)…[XΦ(n)]modn] modn <=同乘a等於係數重排
= [aX1modn aX2modn aX3modn …. [aXΦ(n)]modn ] modn <- 將a提出
=aΦ(n) [X1*X2*X3..XΦ(n)]modn <= 同乘反元素[X1*X2*X3..XΦ(n)]-1
1 mod n= aΦ(n)
3. 寫出並證明RSA所用的基本定理
RAS基本定理:m代表一個訊息,n=p*q , mΦ(n)+1=m mod n
a.當 (m,n) = 1 根據尤拉定理 aΦ(n) = 1 mod n
mΦ(n)+1=m mod n(兩邊同乘m後得證 )
b.當 (m,n)≠1 所以 b
b
mΦ(q) = 1 mod q
[mΦ(q)] Φ(p)= 1Φ(p)mod q ( 兩邊同乘Φ(p) 次方)
mΦ(n) = 1 mod q (因為 n =p*q,1的任何次方還是1 )
mΦ(n) = 1+kq (存在一整數k,1modq = 1+kq)
mΦ(n+1) =m + kqm (兩邊同乘m)
mΦ(n+1) = m + kqC1p (m =C1*p代入)
mΦ(n+1) = m + kC1n (其中 n=p*q代入)
mΦ(n+1) = m mod n (m+kC1n等於 m mod n)
b
4. 證明 (a+b) mod n = [(a mod n) + (b mod n)] mod n
假設 (a mod n)= Ra (b mod n) = Rb , 則 a = Ra + j n ; b = Rb + kn
(a+b) mod n = [(Ra+jn )+(Rb+kn) ]mod n
= [Ra+Rb+ (j+k)n ] mod n
=(Ra+Rb) mod n <- 根據假設 (a mod n)= Ra (b mod n) = Rb帶入
= [(a mod n )+ (b mod n )] mod n
5. 何謂一個體, 做 Z3 的三個表
體:俱有兩個交換環,並有不具有0的真因子,除0之外皆有反元素
加法 |
0 |
1 |
2 |
0 |
0 |
1 |
2 |
1 |
1 |
2 |
3 |
2 |
2 |
3 |
4 |
乘法 |
0 |
1 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
2 |
0 |
2 |
4 |
w |
-w |
w-1 |
0 |
0 |
0 |
1 |
2 |
1 |
2 |
1 |
2 |
6. 若 Z=k.Φ(n)+q 則 az = ? mod n
az =a k.Φ(n)+q = [aΦ(n)]k * aq
= {[(aΦ(n))k modn ][aqmodn]}modn (根據尤拉 aΦ(n)=1modn )
= {(1modn)(aqmodn)}modn
=a^q modn
7. 說明 discrete logarithm problem
離散對數依照方程式: y=gx mod p
給定g x p 可以很快算出 y ,但是只給 y g p 則很難算出 x的值。
8. 用 Euclid algorithm 求 GCD(86,32)
GCD(86,32)
86=2*32+22 GCD(32,22)
32=1*22+10 GCD(22,10)
22=2*10+2 GCD(10,2)
10=2*5+0 得 GCD(86,32)=2