博主是初学初等数论（整除+同余+原根），本意是想整理一些较难理解的定理、算法，加深记忆也方便日后查找；如果有错，欢迎指正。 我整理成一个系列：初等数论，方便检索。
和费马素性检测算法思路是一致的，都是已知公式推素数概率，只是这里的公式条件更强了，费马素性检测算法是通过伪素数的公式，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素性检测。”
