Miller–Rabin

Definition 定义

Miller–Rabin 指“米勒–拉宾素性测试”：一种快速的概率型算法，用来判断一个整数是否为素数（或判定其为合数）。它通过选取若干“底数（bases）”进行模幂运算；若出现“见证（witness）”，即可确定为合数；若多次测试都未发现见证，则该数很可能是素数（存在极小概率误判为“强伪素数”）。也常用于密码学中的大素数生成。

Pronunciation 发音（IPA）

/ˈmɪlər ˈreɪbɪn/

Examples 例句

The program uses the Miller–Rabin test to check if a number is prime.
该程序使用米勒–拉宾测试来检查一个数是否为素数。

To generate RSA keys efficiently, many libraries run Miller–Rabin with several random bases to filter out composite candidates before doing heavier checks.
为高效生成 RSA 密钥，许多库会用多个随机底数运行米勒–拉宾测试，先筛掉合数候选，再进行更耗时的进一步验证。

Etymology 词源

“Miller–Rabin” 来自两位研究者的姓氏：Gary L. Miller 与 Michael O. Rabin。Miller 在特定数论假设下给出确定性思路，Rabin 将其发展为广泛使用的概率性素性检验形式，因此合称 “Miller–Rabin test”。

Related Words 相关词汇

• Primality Test
• Fermat Test
• Composite
• Witness
• Pseudoprime
• Carmichael Number
• Modular Exponentiation
• RSA
• Probabilistic Algorithm
• Number Theory

Literary Works 文献与作品（出现或讨论该术语）

• Michael O. Rabin, Probabilistic algorithm for testing primality（1980）
• Gary L. Miller, Riemann’s Hypothesis and Tests for Primality（1976）
• Thomas H. Cormen et al., Introduction to Algorithms（常在素性测试/数论相关章节提及）
• Neal Koblitz, A Course in Number Theory and Cryptography（密码学中的素性测试讨论）
• William Stallings, Cryptography and Network Security（常见于密码学工程背景下的素性检测说明）