*奇想西卡*

1. 寫出並證明費碼定理

Fermat 定理 ，當 (a,p)=1 (a跟p互質)

a. a^p-1 = 1 mod p

證明：在Zp 之中 a、p互質

[1*2*3..*(p-1)]modp={(1*a)(2a)(3a)...[a(p-1)]}modp <-同成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 -> a^p-1 = 1 mod p

b. a^p = a mod p

證明：假設 (a,p)≠1 則 a為p的倍數 並可寫成a^p≠a mod p

a^p≠a mod p

a^p –a ≠ (a-a) mod p (兩邊同減a)

a(a^p-1 –1) ≠ 0 mod p (左邊將a提出)

∵a(a^p-1 –1) ≠ 0 mod p

∴ p不整除 a 且p不整除 (a^p-1 –1)

與假設不符合所以得證 a^p=a mod p

2. 寫出並證明尤拉定理

尤拉定理 ，當 (a,p)=1 (a跟p互質)

a. 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 (右邊將a提出)

1 mod n= a^Φ(n) (左右同乘反元素[X1*X2*X3..XΦ(n)]^-1)

得證：a^Φ(n)＝1 mod n

b. 當 (a,n)≠1　且(a<n) ，a^Φ(n＋1)＝a mod 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-1 m = C1p b-2 m = C2q

b-1 m = C1 * p , (m , q) = 1 根據尤拉定理可寫為　

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-2 m = C2*q 同 b-1 可證 m^Φ(n+1) = m mod n

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. 何謂一個體, 做 Z₃ 的三個表

體：除了0之外，有兩個交換環(加法和乘法)，加法和乘分具分配律，並有不具有0的真因子，除0之外皆有反元素

6. 若 Z=k．Φ(n)+q 則 a^z = ? mod n

a^z =a ^k．Φ(n)+q = [a^Φ(n)]^k * a^q

= {[(a^Φ(n))^k modn ][a^qmodn]}modn (根據尤拉 a^Φ(n)＝1modn )

= {(1modn)(a^qmodn)}modn

=a^q modn

7. 說明 discrete logarithm problem

離散對數依照方程式： y=g^x 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