无需登录 数据私有 本地保存

大数素数检测 - 米勒-拉宾算法演示

19
0
0
0

大数素数检测 - 米勒-拉宾算法

基于 Miller-Rabin 概率素数检测算法，支持任意大整数，展示完整检测步骤与模幂运算过程

支持任意长度整数，可包含数字分隔空格（自动清理）
快速示例：
常见问题与知识点
什么是 Miller-Rabin 素数检测算法？
Miller-Rabin 算法是一种概率性素数检测算法，由 Michael O. Rabin 基于 Gary Miller 的工作提出。它能在多项式时间内判断一个大整数是否为合数，或者以极高概率判定为素数。与试除法不同，它的时间复杂度为 O(k·log³n)，其中 k 是检测轮数，非常适合检测数百位甚至上千位的大整数。该算法广泛应用于密码学（如 RSA 密钥生成）和计算机代数系统中。
Miller-Rabin 算法的核心原理是什么？
算法基于费马小定理的推广：对于素数 n，如果 n-1 = d·2s（d 为奇数），则对任意与 n 互素的基数 a，序列 {ad, a2d, ..., a2sd} mod n 要么以 1 开头，要么在某处出现 n-1。如果某个基数不满足此条件，n 一定是合数。算法的精妙之处在于：每轮检测最多只有 1/4 的概率误判合数为素数，因此 k 轮后错误概率降至 4-k。
Miller-Rabin 和试除法有什么区别？
试除法需要尝试所有小于 √n 的素数，对于 100 位的数字，√n 约有 50 位（即 1050），完全不可行。Miller-Rabin 每轮只需 O(log³n) 次运算，检测一个 100 位数字仅需毫秒级时间。不过 Miller-Rabin 是概率性算法（虽然可通过选择特定基数变为确定性），而试除法给出绝对确定的答案。实际应用中，通常先用小素数试除过滤，再使用 Miller-Rabin 进行深度检测。
什么是 Carmichael 数？为什么 561 很特殊？
Carmichael 数（绝对伪素数）是能通过所有基数的费马素性测试的合数。561 = 3×11×17 是最小的 Carmichael 数。对于普通费马测试，561 会被误判为素数。但 Miller-Rabin 算法能有效识别 Carmichael 数——它使用更强的"强伪素数"条件，即便是 561 这样的数，在大多数基数下也会被正确识别为合数。这正是 Miller-Rabin 相比简单费马测试的巨大优势。
如何选择检测轮数 k？错误概率有多大？
每轮 Miller-Rabin 检测的错误概率上界为 1/4（实际远低于此）。选择建议：
• k=3~5：日常使用，错误概率 < 0.1%，足以应对大多数场景
• k=10：错误概率约 10-6，适合安全敏感应用
• k=20：错误概率约 10-12，达到密码学标准
• k=40~64：RSA 密钥生成等关键场景
对于小于 264 的数，使用前 12 个素数作为基数可得到确定性结果。
什么是确定性 Miller-Rabin？
对于特定范围内的整数，使用已知的固定基数集合可获得确定性结果（即100%正确）。例如：n < 264 时使用前12个素数（2,3,5,7,11,13,17,19,23,29,31,37）即可；n < 3.3×1024 时使用前13个素数。更大的范围也有对应的基数集合（如 Jaeschke、Sinclair 等人的研究成果）。本工具使用前 k 个小素数作为基数，对于范围内的数字可提供确定性判断。
大数素数检测有哪些实际应用？
主要应用包括：RSA 加密（需要生成数百位的大素数）、Diffie-Hellman 密钥交换、ElGamal 加密、数字签名（DSA/ECDSA）、区块链（零知识证明中的素数）、伪随机数生成等。实际上，每次您访问 HTTPS 网站时，背后的 RSA/ECDH 握手都依赖于 Miller-Rabin 算法来生成安全素数。可以说，它是现代互联网安全的基石之一。
模幂运算（快速幂）在算法中的作用？
模幂运算 ad mod n 是 Miller-Rabin 的核心计算。使用朴素方法（连续乘 d 次）对于大指数完全不可行。本工具使用"平方-乘"快速幂算法（Square-and-Multiply）：将指数 d 转为二进制，通过反复平方和选择性乘法，将时间复杂度从 O(d) 降至 O(log d)。例如计算 a1000 仅需约 10 步而非 1000 步，对于数百位的大指数，这是唯一可行的方法。
🔧 相关工具