《算法的乐趣》第五十六节

米勒-拉宾素性检验算法源于米勒教授基于广义黎曼猜想提出的确定性算法，后经拉宾教授改进为不依赖该假设的随机化算法。

米勒-拉宾素性检验算法源于米勒教授基于广义黎曼猜想提出的确定性算法，后经拉宾教授改进为不依赖该假设的随机化算法。该算法通过随机选取整数a，对n进行多次检验来判断其是否为合数：若满足特定条件则n是合数，否则n有75%的概率是素数。通过增加检验次数可显著降低误判率，例如检验5次后n是素数的概率可达99.9%。在特定数值范围内，该算法可作为确定性算法使用。

RSA算法是一种非对称公钥加密算法，其安全性基于大素数乘积难以分解的数学难题。密钥生成过程包括：选取两个大素数p和q，计算公共模数n和欧拉函数φ(n)，选择与φ(n)互素的加密指数e，求解对应的解密指数d。加密和解密过程均为模幂运算。算法安全性与密钥长度、素数选择及加密指数e的选择有关，通常需要填充随机值以抵抗小指数攻击。