Miller-Rabin Test

释义 Definition

Miller–Rabin 测试（米勒–拉宾素性测试）：一种用于判断一个整数是否为素数的算法，常见于密码学与大整数计算中。它属于概率型素性测试：若判定为“合数”则一定正确；若判定为“可能为素数”，则仍有极小概率其实是合数（可通过多轮测试把出错概率降得极低）。也常简称 Miller–Rabin。

发音 Pronunciation (IPA)

/ˌmɪlər ˈreɪbɪn tɛst/

例句 Examples

The Miller-Rabin test helps us quickly check whether a number is prime.
米勒–拉宾测试帮助我们快速检查一个数是否为素数。

In modern cryptography, implementations often run the Miller-Rabin test with several random bases to make the probability of error negligible.
在现代密码学中，实现通常会用多个随机底数重复运行米勒–拉宾测试，使出错概率几乎可以忽略不计。

词源 Etymology

该名称来自两位学者的姓氏：Gary L. Miller 与 Michael O. Rabin。Miller 提出了相关的思路（与特定假设下的确定性方法有关），Rabin 随后给出了广泛使用的随机化/概率版本，因此合称 Miller–Rabin。

相关词 Related Words

• Primality Test
• Fermat Test
• Prime
• Composite
• Witness
• Pseudoprime
• Probabilistic
• Deterministic
• Modular Arithmetic
• Cryptography

文学与著作 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）中在数论/随机算法相关章节提到该测试
• Handbook of Applied Cryptography（Menezes, van Oorschot, Vanstone）中在素性测试与大整数算法部分讨论 Miller–Rabin
• Applied Cryptography（Bruce Schneier）中在密钥生成与素性检测相关内容提及素性测试（包括 Miller–Rabin）