[文件] about Miller-Rabin & Pollard-ρ

※前言

關於質數，台灣競賽方面似乎比較少提及，頂多學學篩法、根號檢驗法而已。

草提一下這兩個算法：



>>埃氏篩法：




//什麼毛啦顏色傳上來變得醜死了


O(N ln N)時間複雜度、O(N)記憶體，求出1~N所有的質數。

    一些優化：

        1. 僅 型如 6n ± 1 者有可能是質數（2 | 6n+2、3 | 6n+3、2 | 6n+4）

        其實這個優化加下去已經可以達到一定速度了。


        2. 用位元壓縮，記憶體僅需要(N/32)個int（排掉偶數可以剩下N/64，但個人認為沒必要）

    一些應用：

        1. 求出質因數個數：

            值得注意的是I = i*i要改成I = i+i才行。

        2. 求Φ(n)：

            即找出1~n-1中有幾個跟n互質的數。

            因為有Φ(n) = n * Π(1 - (1/p))     對每個質數p | n，所以可以用篩法作到。



// 另外，線性篩法我不會，所以省略...

相關題目：
    TIOJ：1036、1260、1353、1514、1535
    ACM：294




>>根號檢驗法：




O(√n)檢驗一個數是否為質數。

    一些應用：

        1. 質因數分解：

            每次除到不能除，若<= √p都試完了剩下的那個一定是質數。


相關題目：
    ACM：583



反正目前為止的台灣競賽幾乎都只注重以上兩者，相關題目也十分罕見（目前為止沒見過）

但是對於密碼學而言，以上算法都還不能讓人滿意。




>>Miller-Rabin：

一個能期望極快的判斷質數作法。

算法核心：

引理一：若p是質數，則a^(p-1) mod p = 1 （費瑪小定理）

引理二：若x² mod p = 1（其中x<p、p是質數）那x = p-1或x = 1 （證明就是用(x+1)(x-1) = kp）

然後若我們要測定n是否能通過以a為底的米勒拉賓測試
先把n-1 = 2^r * d ， 其中d是奇數   也就是求出n-1最高含2的幾次方



那麼   如果 a ^{(2r * d)} mod n 不是1  就一定是合數 （引理一）
       就繼續下去a ^{(2(r-1) * d)} mod n 得是n-1 或1（引理二）
       如果是n-1即是通過檢測，如果是1就繼續遞迴直到 a^d mod n


對int範圍的數字，只需要測 a = 2, 7, 61
對10^16內的數字，只需要測 a = 2, 3, 5, 7, 11, 13, 17, 61, 24251



所以只需要寫一個大數次方 + 主程序大概 20~30 行很OK。


虛擬碼就不附了，上次寫得爛爛的。

進一步可以參照Matrix67的相關文章。




>>Pollard-ρ：

還在學...