Strong Pseudoprime

释义 Definition

强伪素数：指某个合数在特定的素性检验（最常见是 Miller–Rabin（米勒–拉宾）检验）下，表现得“像素数一样”通过测试的数。它比普通的“费马伪素数（Fermat pseudoprime）”条件更严格，因此称为“strong（强）”。

发音 Pronunciation (IPA)

/strɔŋ ˈsuːdoʊpraɪm/
/strɒŋ ˈsjuːdəʊpraɪm/

例句 Examples

A strong pseudoprime can fool a primality test.
强伪素数可能会欺骗素性检验。

Although 341 is composite, it is a strong pseudoprime to some bases in the Miller–Rabin test, so one base is not enough for certainty.
虽然 341 是合数，但在米勒–拉宾检验中它对某些底数是强伪素数，因此只测一个底数并不足以保证结论可靠。

词源 Etymology

pseudoprime 由 pseudo-（“假的、伪的”）+ prime（“素数”）构成，字面意思是“看起来像素数的数”。加上 strong，表示它满足的是更强、更严格的一类“伪装成素数”的条件（典型地对应 Miller–Rabin 的“强”条件），比仅满足费马小定理的伪素数更不容易出现，但仍然存在。

相关词 Related Words

• Composite
• Prime
• Pseudoprime
• Fermat Pseudoprime
• Carmichael Number
• Miller-Rabin Test
• Probable Prime
• Witness
• Modular Arithmetic

文献与作品 Literary / Notable Works

• Prime Numbers: A Computational Perspective（Richard Crandall, Carl Pomerance）——讨论素性检验与（强）伪素数在计算数论中的角色。
• Handbook of Applied Cryptography（Menezes, van Oorschot, Vanstone）——在密码学背景下介绍 Miller–Rabin 检验及相关概念（包括强伪素数/可能素数）。
• “The pseudoprimes to 25·10^9”（Pomerance, Selfridge, Wagstaff, 1980）——经典论文之一，系统研究伪素数（与强伪素数相关的筛选与统计）。