素数 · aiwiki.page

素数是大于1且恰有两个正因数（1和自身）的正整数。最初的几个素数是2、3、5、7、11、13、17、19、23和29。大于1而不是素数的数称为合数。素数在数论中占据核心地位，因为每个大于1的整数都可以表示为素数的乘积，而且除因子的排列顺序外，这种表示是唯一的。(users.math.msu.edu)

定义与基本性质

判断一个数是否为素数，考察的是整数范围内的整除关系，而不是允许商为任意分数的除法。例如，7是素数，因为除了1和7以外，没有其他正整数能将它整除；12是合数，因为 $12=3\times4$ 。1既不是素数，也不是合数，因为它只有一个正因数。将1排除在素数之外，也避免了在素因数分解中任意插入多个因子1。(math.gordon.edu)

2是唯一的偶素数，因为每个大于2的偶整数都以2为真因数。每个合数 $n$ 都有一个不大于 $\sqrt n$ 的素因数。因此，要判断 $n>1$ 是否为素数，只需检查不超过这一上界的素数能否整除它。(math.uwaterloo.ca)

欧几里得引理给出了素数的一项基本性质：如果素数 $p$ 整除乘积 $ab$ ，那么 $p$ 整除 $a$ 或 $b$ 。对于一般的合数除数，类似的命题并不成立：6能整除 $2\times3$ ，却不能整除其中任何一个因子。(math.mit.edu)

素因数分解

算术基本定理指出，将素数按固定顺序排列后，每个整数 $n>1$ 都有唯一的表示形式：

n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},

其中， $p_i$ 是互不相同的素数， $a_i$ 是正整数。例如，

360=2^3\cdot3^2\cdot5.

不断将合数因子分解为更小的因子，即可证明这种分解的存在性；利用欧几里得引理则可证明其唯一性。因此，素数是构成正整数的乘法基本单元，但在加法运算下，并不存在类似的唯一分解。(math.gordon.edu)

素数有无穷多个

对素数的研究可以追溯到古希腊。欧几里得在《几何原本》第九卷中证明了素数有无穷多个。一种常见的现代论证采用反证法：假设 $p_1,\ldots,p_k$ 就是全部素数，并构造

N=p_1p_2\cdots p_k+1.

列出的素数都不能整除 $N$ ，因为 $N$ 除以其中任何一个素数的余数都是1。然而， $N>1$ 必定有一个素因数，这就与该列表包含全部素数的假设矛盾。需要注意的是， $N$ 本身不一定是素数；这一论证只要求它有一个不在所列素数中的素因数。(faculty.etsu.edu)

分布

随着数值增大，素数平均而言会变得越来越稀疏。用 $\pi(x)$ 表示不超过 $x$ 的素数个数。素数定理指出：

\pi(x)\sim\frac{x}{\ln x},

这意味着，当 $x$ 无限增大时，两边表达式的比值趋于1。雅克·阿达马和夏尔-让·德拉瓦莱·普桑于1896年分别独立证明了这一定理。它描述的是素数的平均密度，而不是精确确定每个素数位置的规则。(claymath.org)

此外，还存在任意长的连续合数序列。对于任意整数 $m\ge2$ ， $m!+2,\ldots,m!+m$ 都是合数，因为每个 $m!+j$ 都能被 $j$ 整除。这表明素数间隔没有上界。(math.uwaterloo.ca)

对素数分布更深入的描述涉及黎曼ζ函数。波恩哈德·黎曼于1859年提出的黎曼猜想断言，该函数所有非平凡零点的实部都为 $1/2$ 。克雷数学研究所仍将这一猜想列为未解问题。它对素数研究的重要意义，在于能够精确控制素数分布相对于平均分布的偏差。(claymath.org)

寻找素数与素性测试

埃拉托斯特尼筛法是一种用于列出给定上界以内全部素数的算法。它从2开始列出整数，反复将当前最小的未标记数的倍数标记出来。只需依次处理平方不超过上界的素数；最终剩下的未标记整数就是素数。(users.math.msu.edu)

对于单个很大的输入整数，素性测试与求出其完整的因数分解是不同的任务。费马小定理指出，对于素数 $p$ 和不能被 $p$ 整除的整数 $a$ ，有

a^{p-1}\equiv1\pmod p.

然而，仅仅满足这一同余式并不能证明一个数是素数。米勒–拉宾素性测试通过检查更多的模幂运算结果，增强了此类测试的判别能力。采用独立随机选择的参数重复测试，可以降低合数输入通过所有轮次测试的概率。(math.mit.edu)

2002年，马宁德拉·阿格拉瓦尔、尼拉杰·卡亚尔和尼廷·萨克塞纳提出了AKS素性测试。它无需假定任何尚未证明的猜想，就能以确定性的方式，在相对于输入位数的多项式时间内判定素性。这是计算复杂性领域的一项里程碑成果，但并不意味着整数因数分解也有了多项式时间算法。(cse.iitk.ac.in)

代数与密码学

在模算术中，模素数 $p$ 的剩余类构成一个有限域：每个非零剩余类都有乘法逆元。模合数的剩余类则不具备这一性质。因此，素数确定了一种重要的代数结构，在这种结构中，可以进行以非零元素为除数的除法。(math.mit.edu)

素数也是密码学中部分方法的基础。在RSA密码系统中，模数由两个互不相同的大素数相乘构成。知道这两个因子，就能计算出构造私钥所需的信息。高效的素性测试为密钥生成提供支持，而从乘积中还原其因子的困难性则是这一系统的核心安全性假设。(math.mit.edu)