Primality Test

Definition / 定义

primality test：素性测试（质数判定），指用来判断一个正整数是否为质数（只能被 1 和它本身整除）的算法或方法。（在数论与密码学中非常常见）

Pronunciation / 发音（IPA）

/praɪˈmælɪti tɛst/

Examples / 例句

A primality test can tell if 97 is prime.
素性测试可以判断 97 是否为质数。

Modern cryptography relies on fast primality tests to generate large primes for encryption keys.
现代密码学依赖快速的素性测试来生成用于加密密钥的大质数。

Etymology / 词源

primality 来自 prime（质数/首要的），其拉丁语根与“第一、主要”有关；在数学语境里 prime number 表示“质数”，于是 primality 表示“质数性质（素性）”。test 表示“检验/测试”。合起来就是“对一个数是否具备质数性质的检验”。

Related Words / 相关词汇

• Prime
• Composite
• Divisor
• Factor
• Modular
• Algorithm
• Cryptography
• Sieve

Notable Works / 文学与著作中的用例

• The Art of Computer Programming, Volume 2: Seminumerical Algorithms（Donald E. Knuth）：讨论多种与素数与primality testing相关的算法思想。
• Introduction to the Theory of Numbers（G. H. Hardy & E. M. Wright）：在数论框架下涉及质数判定与相关理论背景。
• Prime Obsession（John Derbyshire）：面向大众介绍素数问题时会谈及判定质数的思路与方法。