Fermat Test

定义 Definition

费马检验（Fermat test）是一种用于快速判断一个整数是否可能为素数的数论方法。它基于费马小定理：若 \(p\) 为素数且 \(a\) 与 \(p\) 互素，则 \(a^{p-1}\equiv 1\pmod p\)。若对某个底数 \(a\) 不成立，则该数一定是合数；若成立，则只是“可能是素数”（因为存在费马伪素数/卡迈克尔数会骗过检验）。

发音 Pronunciation (IPA)

/fərˈmɑː tɛst/

例句 Examples

Fermat test can quickly rule out many composite numbers.
费马检验可以快速排除许多合数。

Although the Fermat test is fast, cryptographic systems usually combine it with stronger methods to reduce the risk of pseudoprimes.
尽管费马检验速度很快，密码系统通常会把它与更强的检验方法结合使用，以降低伪素数带来的风险。

词源 Etymology

“Fermat”来自法国数学家皮埃尔·德·费马（Pierre de Fermat, 1607–1665）的姓氏；“test”意为“检验/测试”。“Fermat test”即“基于费马相关定理的素性检验方法”，在计算数论与密码学中常用作快速筛查。

相关词 Related Words

• Primality
• Prime
• Composite
• Modular
• Congruence
• Pseudoprime
• Carmichael
• Miller-Rabin

文学与著作中的出现 Literary Works

• G. H. Hardy & E. M. Wright，《An Introduction to the Theory of Numbers》：在讨论费马小定理与素性判定思路时涉及费马检验的思想背景。
• Richard Crandall & Carl Pomerance，《Prime Numbers: A Computational Perspective》：系统介绍计算数论中的素性测试，包括费马检验及其局限（伪素数、卡迈克尔数）。
• Neal Koblitz，《A Course in Number Theory and Cryptography》：在密码学所需的大数素性检测语境中讲到费马类测试与更强检验的搭配使用。