[Cryptography] 數論相關筆記-Fermat and Euler

Fermat's theorem之定義是，若p是一個質數，則存在一個x，x比p小且互質，x會滿足下列式子：

x^p-1 = 1 in Z_p

在應用上，可以用來簡化次方的運算，譬如說：

2¹⁰⁰⁰¹ mod 11

2與11互值，所以2^(11-1)次方，其值會等於1。所以計算是變成

2¹⁰⁰⁰¹ mod 11 = 2^(10000+1) mod 11 = 2^10*1000*2¹ mod 11 = 1¹⁰⁰⁰ * 2 mod 11 = 2 mod 11

可以快速計算出答案為2。

Euler's theorem其實概念與Fermat's theorem有點類似，但是差別在於如果今天p是質數，則：

φ(p)=p-1

舉例來說，與比7小寫互質的數有1, 2, 3, 4, 5, 6，總共6個，也就是7-1=6個。φ(p)代表著比p小且互質的數，但不限於p是質數。像是φ(12) = 4，因為與12互質的數字是1, 5, 7, 11。

至於For N=p*q: φ(N) = N-p-q+2 = (p-1)(q-1)，這段其實我沒有很了解，但是在wiki我找到更好的例子：

所以φ(12)=12*(1-1/2)(1-1/3)=12*(1/2)*(2/3)=4。

這樣就可以用來計算範例啦。

2²⁴⁵ mod 35

利用Euler's theorem先算

φ(35)=35*(1-1/5)*(1-1/7)=35*(4/5)*(6/7)=24

接著由x^φ(N)=1 in Z_N可以推得

2²⁴ = 1 mod 35

所以，原式變成

2^24*10+5 mod 35 = 2⁵ mod 35 = 32 mod 35

答案就是32囉。

綜合來說，Euler's theorem與Fermat's theorem定義其實就是，有一個數字p，則存在一個數字x，比p小且與p互質。接著p中，比p小且互質的數字共有φ(N)個，則x的φ(N)次方取p餘數後，其值為1。