米勒-拉賓質數判定算法

習題預習

1. 什麼是Miller-Rabin Algorithm (MRA)？它與其他素性測試算法的區別是什麼？
2. MRA如何判斷一個數是否為質數？它的運行時間是多少？
3. MRA在什麼情況下可能會給出錯誤的結果？該如何解決這個問題？
4. MRA是否可應用於大數據範圍內的質數判斷？如果可以，需要注意哪些問題？
5. MRA的應用場景有哪些？該算法的優點和缺點是什麼？

說明知識

Miller-Rabin Algorithm是一種概率性質質數測試法，用於檢測一個數字是否為質數。它基於Fermat’s Little Theorem和二次剩餘的性質，在確定一個數字是否為質數時，比起其他傳統的質數測試算法，如暴力測試法或埃拉托色尼質數篩法，更加高效。

Miller-Rabin Algorithm的演算法流程如下：

1. 將欲判斷的數字n-1表示成 2^s * d 的形式，其中d為奇數。
2. 隨機選擇一個小於n的整數a作為底數。
3. 計算a^d mod n，若 a^d ≡ 1 (mod n) 或 a^(2^r * d) ≡ -1 (mod n) 就判定這是質數或可能是錯誤的。其中r∈[0,s-1]
4. 如果驗證不是質數，則繼續對a重新選擇底數，重複步驟2-3，若經過k次驗證皆為質數或可能是錯誤的，就判定n為質數；若經過k次驗證存在不合法的結果，就判定n為合數。

以下是一個Miller-Rabin Algorithm的例子：

我們想要確認60是否為質數。

1. 60-1可以表示成 2^2 * 15的形式。
2. 選擇一個隨機底數a = 2。
3. 計算2^15 mod 60，得到32。
4. 因為2^30 ≡ 1 (mod 60)，所以我們可以進行以下的判斷式：

2^2 * 15 = 60-1
2^15 ≡ 32 (mod 60)
2^30 ≡ 1 (mod 60)

因此，2^60 ≡ (2^30)^2 ≡ 1 (mod 60)，所以60可能是錯誤的質數，我們需要繼續進行驗證。

5. 我們再次選擇底數a = 7。
6. 計算7^15 mod 60，得到49。
7. 我們也可以進行以下的判斷式：

7^2 ≡ 49 ≡ -11 (mod 60)
7^4 ≡ (-11)^2 ≡ 121 ≡ 1 (mod 60)

因此，7^15 ≡ (7^4) * (7^4) * 7^2 ≡ 1 (mod 60)，所以60可能是錯誤的質數，我們需要再次繼續驗證。

8. 我們再次選擇底數a = 11。
9. 計算11^15 mod 60，得到49。
10. 進行以下判斷：

11^2 ≡ 1 (mod 60)
11^4 ≡ 1 (mod 60)

因此，11^15 ≡ (11^4) * (11^4) * 11^2 ≡ 1 (mod 60)，所以我們可以確定60是錯誤的合數。

因此，我們可以確定60是錯誤的合數，不是質數。 如此反覆執行，直到分別執行了k次測試都沒有成功，我們才能夠大致得到一個數字是否是質數。

彙總重點

1. Miller-Rabin算法是一種用於快速判定一個數是否為素數的概率算法。
2. 這種算法基於費馬小定理以及阿基米德反演等數論知識，通過隨機選取若干個基數來檢測是否為素數。
3. Miller-Rabin算法針對偽素數的概率給出了一個極小值，因此在實際應用中已經被廣泛使用。
4. 通過設置適當的檢測次數，可以將檢測出錯的概率降到極低，從而確定一個數是否為素數。
5. 由於複雜度相對較低，Miller-Rabin算法被廣泛地應用在計算機理論、加密系統等領域。

知識測驗

1. 對於一個給定的奇數 n，假設 a 是其中一個小於 n 的整數。如何使用 Miller-Rabin Algorithm 驗證 a 是否是 n 的一個質數證人？

答案：以 k 次隨機選取的 a 為例，將 n - 1 表示為 d * 2^s 的形式，其中 d 是奇數，s >= 1。接下來用快速冪算法計算 a^d mod n，如果得到的結果等於 1 或 n - 1，停止計算，並認為 a 是 n 的可能質數證人。如果結果不等於 1 或 n - 1，計算 a^(2^r * d) mod n，直到 r = s 或得到的結果等於 n - 1。如果最後得到的結果等於 n - 1，則仍認為 a 是 n 的可能質數證人。否則認為 a 不是 n 的質數證人。

2. 使用 Miller-Rabin Algorithm 求一個大質數（大於 10^10）的可能質數證人。

答案：多次隨機選取 a 進行測試，如果每次測試都得到 a 為 n 的可能質數證人，則有很高的概率認為 n 是質數。要注意選取的 a 需要小於 n，可使用隨機數生成器達到這個目的。

3. 對於一個給定的奇數 n，使用 Miller-Rabin Algorithm 找到一個質數 p，使得 n - p 是一個平方數。

答案：如果 n 是質數，則 p = 2 是說是可以的。如果 n 不是質數，則可以隨機選取 a 進行測試。如果得到 a 是 n 的一個可能質數證人，則有很高概率認為 n 是合數。此時可以計算 b = sqrt(n - 1)，如果 b 是一個整數，則 p = n - b^2 是一個質數。

4. 對於一個給定的質數 p，使用 Miller-Rabin Algorithm 判斷是否存在一個 a，使得 a 是 p 的原根。

答案：對於 p 的每個質因子 q，如果 q = 2 或 p / q = 2，則 p 中不存在原根。否則，可以使用隨機選取的 a 進行測試。如果得到 a 是 p 的可能質數證人，則有很高概率認為 a 是 p 的原根。此時計算 phi(p) 和其所有質因子的乘積，如果 a^((p-1) / q) mod p 不為 1，對於所有的質因子 q，則認為 a 是 p 的原根。

5. 對於一個給定的奇數 n，使用 Miller-Rabin Algorithm 判斷是否存在一個奇數 g，使得 g 是 n 的原根。

答案：可以隨機選取一個質數 p，使得 p 是 n 的一個質因子。然後選取一個小於 p 的整數 a，計算 g = a^((p-1) * (n-1) / phi(n)) mod n。如果 g 不等於 1，則有很高概率認為 g 是 n 的原根。否則，換一個 a 重新計算。如果 p 不能選出，則需要用更高級的算法解決問題。