[溫故知新,數論] Prmitive Root modulo n

(以下定義/定理或者未夠嚴僅... 數學人請見諒...)

記錄一下每年 "瞬耳即忘" 的數論知識...
雖然網上有很多 material
不過還是親手記下才更深刻
亦好讓日後能循著相似的思路重溫

先來的是在往年的 Training Record 就有提過...
而且(包括算法競賽)應用極廣的：

Theorem 1 (Euler's Totient Theorem)

若 (a, n) = 1
則 a^Φ(n) ≡ 1 (mod n)

---

Definition 1 (Multiplicative Order)

a 的 (multiplicative) order modulo n 是最小的 h
使得 a^h ≡ 1 (mod n)

以下為 (hopefully) 較直觀的解說：

a 的 order 就是 {x_i} 的最小循環節
其中 x₁ := 1 (mod m), x_k :=  x_k-1 × a (mod n)

---

Definition 2 (Primitive Root)

　a 是 modulo n 的 primitive root
⇔ a 的 order 是 Φ(n)

(可以證明： n 一共有 Φ(Φ(n)) 個 primitive root)

---

Corollary 1 (Verifying a primitive root)

　g 是 modulo n 的 primitive root
⇔ 對於每個質因數 p | n ， 有 g^Φ(n)/p ≢ 1 (mod n)

(證明略過，待重溫時檢驗理解程度之深淺用)

然後就是本篇 entry 重點

如何找出(最小的)一個 primitive root modulo n：

數學家(?)暫時仍未發現公式

不過就存在一個足夠快的算法

...就是「頹試」：

Algorithm 1 (Finding the least primitive root)

// Generally very fast... (someone proved...)
Function FindTheLeastPrimitiveRoot(Input n)
　　S ← Set of all prime factors of Φ(n) 
　　For g := 2 to n-1
　　　　If gΦ(n)/p ≢ 1 (mod n) for each p ∈ S  // c.f., Corollary 1
　　　　　　Return g
　　　　EndIf 
　　EndFor 
EndFunction

---

接下來是 Primitive root 其中一個應用：

Application 1 (Finding n, s.t., xⁿ ≡ b (mod m))

Let g := a primitive root modulo m
Preprocess Inv[y] := u  where  gu ≡ (mod m)  //如果 Φ(m) 很小
Express b ≡ gu (mod m) //利用 Inv[] 或 Discrete Logarithm
Let     x ≡ gt (mod m)
Then, we have tn ≡ u mod(Φ(m)) 
We can solve t and thus x easily (or know its non-existence)

不過當 Φ(m) 數值很大，不能打表時
就要動用 Discrete Logarithm 算法...
(詳情再次忘記了，待重溫)