Miller-Rabin Primality Test
Miller-Rabin 是概率素性测试：将 n-1=2^s*d，检查 a^d≡1 或某 a^(2^r*d)≡-1 (mod n)，误判概率≤1/4。
用途
高效概率素性测试，用于 RSA 大素数生成。
机制
对 n-1=2^s*d，随机选 a∈[2,n-2]，计算 x=a^d mod n。若 x=1 或 n-1 则可能素数。否则平方 s-1 次，若出现 n-1 则可能素数，否则确定合数。重复 k 轮误判≤4^(-k)。
用例
- RSA 素数生成
- 素性测试
- 密码学实现