# Prime --- ### 主講人： 簡子軒、邱怡涵、林政啟 地點：S515 日期：109/10/16 --- ### 目錄 --- 1. Prime Numbers 1. Femat’s & Euler’s Theorems 1. Primality Test --- ### Prime Numbers --- ### 質數定義 --- $x∈Z+,x>1$ is called a prime, $if ∀y∈Z+,1<y<x⇒x(mod y) ≠ 0$ --- ### 算術基本定理 --- 定義 $∀A∈N,A>1,∃n∏i=1p^{a_i}_i=A.$ 其中$p_1<p_2<p_3<⋯<p_n$ 而且$p_i$是一個質數，$a_i∈Z+$ --- 每個大於1的正整數都可以由一個以上的質數乘積計算得到，過程稱為質因數分解，且若以大小順序排序這些質因數，只會有一解代表每個正整數。 $e.g. 660=2∗3∗5∗11$ 而且為了保證定理的唯一性(避免被多次累乘)，1被正式定義為非質數。 --- ### Femat’s & Euler’s Theorems --- ### 費馬小定理 --- 假如$a∈Z+$，$p$是一個質數 如果$a$不是$p$的倍數，這個定理也可以寫成 $a^p−1≡1(mod p)$ 若 $a^p−a$ 是p的倍數 --- 證明(1) --- $a^{(p−1)}≡1 (mod p)$ 因為 a 與 p 互質，且 p 為質數，所以 $A={1,2,3,...,(p−1)}(mod p)$ $B={1×a,2×a,3×a,...,(p−1)×a}(mod p)$ $⇒1×a×2×a×3×a,...,(p−1)×a (mod p)$ $=1×2×3,...,(p−1) (mod p)$ $⇒(a^{(p−1)}−1)×1×2×3,...,(p−1) (mod p)=0$ --- 因為 $1,2,3,...,(p−1)$皆與 $p$ 互質 $⇒a^{(p−1)}−1≡0 (mod p)$ $⇒a^{(p−1)}≡1 (mod p)$ --- 證明(2) --- $a^p≡a(mod p)$ 已知 $a^{(p−1)}≡1 (mod p)$ 成立 $⇒a^{(p−1)}×a≡1×a (mod p)$ $⇒a^{(p)}≡a (mod p)$ --- ### 歐拉定理 --- 歐拉定理為費馬小定理的推廣 當$a∈Z^+,n∈Z^+,gcd(a,n)=1$ 的話 $a^φ(n) ≡ 1 (mod p)$ --- ### 歐拉函數 --- $φ(n)$ 對正整數n，小於或等於n的正整數中與n互質的總個數 $x={n∈Z+|∀y∈{i∈Z+,i≤n},gcd(n,y)=1}$ $φ(1)=1$ （小於等於1的正整數中和1互質的數只有1本身）。 --- 若n是質數的時，$φ(n)=n−1$， 所以歐拉定理變回費馬小定理： $a^{n−1}≡1(mod p)$ $a^n≡a(mod p)$ --- ### Primality Test --- 最入門基礎的質數尋找方式，非常的直觀 基本上就是用兩個for包起來，時間複雜度為O($n^2$) --- 優化 $— 1 ~ √n$ 假設 n 為合數，必定可以拆為 $n=a∗b$ 所以 $a,b$ 必定會有一數小於等於 $√n$ --- ### Sieve of Eratosthenes --- 給定一範圍 2~n 所使用的原理是從2開始 將每個質數的各個倍數篩除 剩餘的皆會是質數 --- ```cpp bool prime[20000000]; void eratosthenes(){ for (int i=0; i<20000000; i++) // 初始化 prime[i] = true; prime[0] = false; // 0 和 1 不是質數 prime[1] = false; // 找下一個未被刪掉的數字 for (int i=2; i<20000000; i++) if (prime[i])// 刪掉質數i的倍數，從兩倍開始。保留原本質數。 for (int j=i+i; j<20000000; j+=i) prime[j] = false; } ``` --- ### Linear Sieve Algorithm --- 從上一張的埃式篩，我們能夠發現這是可以被優化的，在埃式篩一個數可能會被多次檢查 ( 像是 $210=2∗3∗5∗7$ ，就會被檢查到4次 )，這樣的時間就被浪費。 --- ```cpp bool sieve[N]; void linear_sieve() { vector<int> prime; for (int i=2; i<N; i++) { if (!sieve[i]) prime.push_back(i); for (int j=0; i*prime[j]<N; j++) { sieve[i*prime[j]] = true; if (i % prime[j] == 0) break; } } } ``` --- ### 費馬質數判定法 --- 缺點: 不保證找出的質數必為質數，可能存在偽質數 應用: 加密程序PGP在算法當中用到了這個質性檢驗方法 --- ### 判斷n是不是質數 --- ``` Input n,k; for in range k: a=random(2,n−1) if(an−1≢1(modn)) return False return True ``` --- ### 謝謝大家