初等數論--同餘--MILLER-RABIN素性檢測算法

部落客是初學初等數論（整除+同餘+原根），本意是想整理一些較難了解的定理、算法，加深記憶也友善日後查找；如果有錯，歡迎指正。

我整理成一個系列：初等數論，友善檢索。

和費馬素性檢測算法思路是一緻的，都是已知公式推素數機率，隻是這裡的公式條件更強了，費馬素性檢測算法是通過僞素數的公式，MILLER-RABIN算法是通過強僞素數的公式，推素數機率。

設 n 為 奇 素 數 ， 且 n − 1 = 2 s t , 則 有 以 下 因 數 分 解 式 ： b n − 1 − 1 = b 2 s t − 1 = ( b 2 s − 1 t + 1 ) ⋅ ( b 2 s − 1 t − 1 ) = ( b 2 s − 1 t + 1 ) ⋅ ( b 2 s − 2 t + 1 ) ⋅ ( b 2 s − 2 t − 1 ) = … … = ( b 2 s − 1 t + 1 ) ⋅ ( b 2 s − 2 t + 1 ) ⋅ … … ⋅ ( b 2 0 t + 1 ) ⋅ ( b 2 0 t − 1 ) 即 如 果 b n − 1 − 1 = 0 ， 至 少 以 下 式 子 有 一 個 成 立 ： b 2 s − 1 t = − 1 b 2 s − 2 t = − 1 b 2 s − 3 t = − 1 … … b 2 0 t = − 1 b 2 0 t = 1 設n為奇素數，且n-1=2^st,則有以下因數分解式：\\ b^{n-1}-1\\ =b^{2^st}-1\\ =(b^{2^{s-1}t}+1)·(b^{2^{s-1}t}-1)\\ =(b^{2^{s-1}t}+1)·(b^{2^{s-2}t}+1)·(b^{2^{s-2}t}-1)\\ =……\\ =(b^{2^{s-1}t}+1)·(b^{2^{s-2}t}+1)·……·(b^{2^{0}t}+1)·(b^{2^{0}t}-1)\\ 即如果b^{n-1}-1=0，至少以下式子有一個成立：\\ b^{2^{s-1}t}=-1\\ b^{2^{s-2}t}=-1\\ b^{2^{s-3}t}=-1\\……\\ b^{2^{0}t}=-1\\ b^{2^{0}t}=1 設n為奇素數，且n−1=2st,則有以下因數分解式：bn−1−1=b2st−1=(b2s−1t+1)⋅(b2s−1t−1)=(b2s−1t+1)⋅(b2s−2t+1)⋅(b2s−2t−1)=……=(b2s−1t+1)⋅(b2s−2t+1)⋅……⋅(b20t+1)⋅(b20t−1)即如果bn−1−1=0，至少以下式子有一個成立：b2s−1t=−1b2s−2t=−1b2s−3t=−1……b20t=−1b20t=1

強僞素數： 如 果 n 是 奇 合 數 ， 且 n − 1 = 2 s t , 其 中 t 為 奇 數 ， 對 于 b ∈ Z , ( b , n ) = 1 , 如 果 b 和 n 滿 足 條 件 b t ≡ 1 ( m o d n ) , 或 存 在 整 數 r , 0 ≤ r < s , 使 得 b 2 r t ≡ − 1 ( m o d n ) , 則 稱 n 為 對 于 基 b 的 強 僞 素 數 。 如果n是奇合數，且n-1=2^{s}t,其中t為奇數，對于b\in Z,(b,n)=1,如果b和n滿足條件b^t\equiv 1(mod n),或存在整數r,0\le r< s,使得b^{2^rt}\equiv -1(mod n),則稱n為對于基b的強僞素數。 如果n是奇合數，且n−1=2st,其中t為奇數，對于b∈Z,(b,n)=1,如果b和n滿足條件bt≡1(modn),或存在整數r,0≤r<s,使得b2rt≡−1(modn),則稱n為對于基b的強僞素數。

之後算法流程與費馬素性檢測算法流程思路一緻，從強僞素數公式推素數機率。

對于這個算法，我也有一個問題沒有解決，“如果n是一個奇合數，則至多有 n − 1 4 個 \frac{n-1} 4個 4n−1​個b , 1 ≤ b ≤ n − 1 ,1\le b\le n-1 ,1≤b≤n−1,使得 n n n通過以 b b b為基的MILLER-RABIN素性檢測。”