許多加密法的安全性其實都是建立在數學的難解問題上
比如RSA的安全性就是建立在大數問題與離散對數的難解上
因此基礎數論是作為後面學習各種加密法的奠基

數論

維基百科：Prime Number Theorem

Fermat’s Theorem 費馬定理

費馬大定理

$x^n + y^n= z^n$
當n>2時，找不到一個整數解(x,y,z)

費馬小定理

用來確認某數是不是質數？

$a^p \equiv a (\bmod p)$

若a不是p的倍數，也可寫成
$a^{p-1} \equiv 1 (\bmod p)$

1
2
3
4
5
> p=7
> [i**(p-1) for i in range(1,p)]
[1, 64, 729, 4096, 15625, 46656]
> [i**(p-1) % p for i in range(1,p)]
[1, 1, 1, 1, 1, 1]

或者使用Python內建的pow()函數 

1
2
3
4
5
> p=7
> [pow(i,p-1,p) for i in range(1,p)]
[1, 1, 1, 1, 1, 1]
> [pow(i,p-1) for i in range(1,p)]
[1, 64, 729, 4096, 15625, 46656]

因此7是質數

Euler Totient Function 尤拉總計函數

小於n並與之互質的數的集合長度 $\phi(n)$

  • 如果n是質數，則 $\phi(n) = n-1$
  • 如果n是由兩個質數p, q組成，則 $\phi(n) = (p-1) \times (q-1)$
1
2
3
4
5
6
7
> n=10
> a=3
> r=4
> [i for i in range(1,n) if math.gcd(i,n)==1]
[1, 3, 7, 9]
> len([i for i in range(1,n) if math.gcd(i,n)==1])
4

尤拉定裡

$a^{\phi(n)}\equiv 1 (\bmod n)$

或是改為更廣義的(when a=0 也符合的定義)

$a^{\phi(n)+1}\equiv a (\bmod n)$

此外，若將n用質數p代入：
( 如果p是質數，則 $\phi(p) = p-1$ )
$a^{\phi(n)} = a^{p-1}$
$a^{p-1} \equiv 1 (\bmod p)$
就會等於費馬小定理

1
2
3
4
5
6
7
> n=10
> a=[i for i in range(1,n) if math.gcd(i,n)==1]
> r=len(a)
> r
4
> [pow(x, r, n) for x in a]
[1, 1, 1, 1]

與群有關的尤拉定裡推廣延伸

$a^n=e$ for all $a \in G$ where G is a group with finitely many elements.
以時鐘鐘面舉例來說(mod 12)，會是0~11的循環(12=0)
{0, 3, 6, 9}是一個加法(+3)的子群(Subgroup)，集合長度為4(為12的因數)
固定鐘面0, 3, 6, 9順時鐘移動可以得到其他兩個子群
{1, 4, 7, 10}、{2, 5, 8, 11}
總共有12個數字，子群有4個數字，子群的個數再加上子群的集合長度(4+4+4)等於母群的資料個數。

拉格朗日定理)：子群的集合長度必須是母群的集合長度之因數

Euclid’s Proof

證明了質數的個數是無限的

Consider any finite list of prime numbers p1, p2, …, pn. (反證)
It will be shown that at least one additional prime number not in this list exists.
Let P be the product of all the prime numbers in the list：P = p1p2...pn .
Let q = P + 1. Then q is either prime or not:
這個q除以p1餘數會是1、除以p2餘數會是1….

  • If q is prime, then there is at least one more prime that is not in the list.
  • If q is not prime, then some prime factor p divides q. If this factor p were in our list, then it would divide P (since P is the product of every number in the list); but p also divides P + 1 = q, as just stated. If p divides P and also q, then p must also divide the difference of the two numbers, which is (P + 1) − P or just 1. Since no prime number divides 1, p cannot be on the list. This means that at least one more prime number exists beyond those in the list.

舉例來說，如果q是質數 

1
2
3
4
5
> a=[2,3,5]
> p=math.prod(a)
> q=p+1
> q
31

在這個假設中質數只有2, 3, 5，質數最大是5，所以31不是質數、應該可以被因數分解(但實際上不行)，故而產生矛盾。

如果q不是質數 

1
2
3
4
5
> a=[2,3,5,7,11,13]
> p=math.prod(a)
> q=p+1
> q
30031

在真實的世界裡30031不是質數，可以被分解成59 $\times$ 509
但這個數字做質因數分解卻能找到比假設a中更大的質數
與一開始所說的最大的質數是13互相矛盾

透過上面兩項可以證明質數的個數是無限的。

Prime-counting function 質數計數函數

$\pi(n)$是小於n並且為質數的集合長度：$\pi(n) \sim \frac{N}{\log(N)}$

${\displaystyle \lim _{x\to \infty }{\frac {\;\pi (x)\;}{\frac {x}{\ln(x)}}}=1}$
因為算 $\pi(x)$ 需要花比較多的時間，$\frac{x}{\ln(x)}$ 比較快，當數字逐漸變大時，可以發現 $\pi(x)$ 與 $\frac{x}{\ln(x)}$ 漸趨於1(更準確)

Goldbach’s Conjecture 哥德巴赫猜想

任何大於2的偶數，都能表示成兩個質數的和

Chinese Remainder Theorem 中國餘數定理

維基百科：中國餘數定理