素数搜索算法

“最大素数是2 ^32582657 -1 。 我自豪地声明我记得他所有的数字……都是二进制形式。”
卡尔·波默兰斯

如果自然数只有两个不同的因数：一个和它本身，则称为素数。 寻找素数的任务一直困扰着数学家很长时间。 长期以来，这个问题没有直接的实际应用，但是随着公钥加密技术的出现，一切都发生了变化。 本文讨论了搜索素数的几种方法，这纯粹是出于学术目的，目前已用于密码学中。

Eratosthenes筛

Eratosthenes筛 -由古希腊数学家Eratosthenes提出的算法。 此方法使您可以找到小于给定数n的所有素数。 该方法的实质如下。 取一组2到n的数字。 划掉所有可以除以2的数字，除了2。从集合（我们消除）中，我们转到下一个“未消除”的数字-3，再次划掉所有可被3整除的数字。我们转到下一个剩余的数字-5，依此类推，直到我们到n 。 执行上述步骤后，只有质数将保留在原始列表中。

该算法可以稍作优化。 由于复合数n的除数之一是强制性的 $$$\ leqslant \ sqrt {n}$ ，删除数字可除的数字后即可停止算法 $$$\ sqrt {n}$ 。

维基百科中算法的操作说明：


该算法的复杂度为 $$$O（n \ log \ log n）$ 同时，要存储有关哪些数字被划掉的信息，这是必需的 $$$O（n）$ 记忆。

有许多优化措施可以减少这些指标。 称为车轮分解的技巧是在初始列表中仅包含与前几个素数互质 （例如，小于30）的质数。 从理论上讲，建议采取第一个简单的方法直到 $$$\ sqrt {\ log n}$ 。 这降低了算法的复杂度 $$$\ log \ logn$ 次。 另外，使用所谓的分段来减少存储器消耗。 初始数字集分为大小段 $$$\ leqslant \ sqrt {n}$ 对于每个段，分别使用Eratosthenes筛子。 内存消耗减少到 $$$O（\ sqrt {n}）$ 。

阿特金筛

Atkin和Bershtein提出了一种更好的筛选合成数的算法，称为Atkin筛 。 此方法基于素数的以下三个属性。

物业1

如果n是一个不是质数平方的倍数的正数，则 $$$n \等值1（\ mod 4）$ 。 当且仅当方程的根数为n时，n为素数 $$$4x ^ 2 + y ^ 2 = n$ 奇怪

物业2

如果n是一个不是质数平方的倍数的正数，则 $$$n \等值1（\ mod 6）$ 。 当且仅当方程的根数为n时，n为素数 $$$3x ^ 2 + y ^ 2 = n$ 奇怪

物业3

如果n是一个不是质数平方的倍数的正数，则 $$$n \等值11（\ mod 12）$ 。 当且仅当方程的根数为n时，n为素数 $$$3x ^ 2-y ^ 2 = n$ 奇怪

本文提供了这些属性的证据。

在算法的初始阶段，阿特金筛网是大小为n的数组A， 其中填充了零。 要确定素数，所有 $$$x，y <\ sqrt n$ 。 对于每个这样的对 $$$4x ^ 2 + y ^ 2$ ， $$$3x ^ 2 + y ^ 2$ ， $$$3x ^ 2-y ^ 2$ 和数组元素的值 $$$A [4x ^ 2 + y ^ 2]$ ， $$$A [3x ^ 2 + y ^ 2]$ ， $$$A [3x ^ 2-y ^ 2]$ 增加一。 在算法的最后，具有奇数值的数组所有元素的索引要么是质数，要么是质数的平方。 在算法的最后一步，将剩下的数字平方除掉。

从算法的描述可以看出，Atkin筛的计算复杂度和内存消耗为 $$$O（n）$ 。 当使用车轮分解和分割时，算法的复杂度估计降低为 $$$O（n / \ log \ log n）$ ，并且内存消耗高达 $$$O（\ sqrt {n}）$ 。

梅森数和Luke-Lemer检验

当然，有了这样的复杂性指标，即使是Atkin优化的筛子也不能用来搜索真正的大素数。 幸运的是，可以进行快速测试来检查给定数字是否为质数。 与筛选算法不同，此类测试并非旨在搜索所有素数，它们只能以一定的概率判断一定数量是否为素数。

一种这样的测试方法是Luc-Lemer测试 。 这是简单性的确定性和无条件检验。 这意味着通过测试可以保证数字的简单性。 不幸的是，该测试仅适用于特殊种类的数字 $$$2 ^ p-1$ 其中p是自然数。 这样的数字称为梅森数字。

Luke-Lemer检验声称梅森数 $$$M_p = 2 ^ p-1$ 当且仅当p为素数且 $$$M_p$ 分界 $$$（p-1）$ 序列的成员 $$$S_k$ 递归设置： $$$S_1 = 4，S_k = S_ {k-1} ^ 2-2$ 为 $$$k> 1$ 。

对于数量 $$$M_p$ p位长度，算法的计算复杂度为 $$${\ displaystyle O（p ^ {3}）}$ 。

由于测试的简单性和确定性，已知最大的质数是梅森数。 今天最大的已知质数是 $$$2 ^ {82,589,933} -1$ ，其十进制表示法由24,862,048位数字组成。 您可以在这里欣赏这种美丽。

费马定理和米勒-拉宾检验

已知的梅森素数并不多，因此公钥密码术需要一种不同的搜索素数的方式。 一种这样的方法是Fermat简单性测试 。 它基于费马小定理，该定理指出，如果n是素数，那么对于任何不能被n整除的a ，等式 $$$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ 。 定理的证明可以在Wikipedia上找到。

Fermat简单性检验是一种概率检验，涉及枚举a的多个值（如果其中至少一个满足不等式）。 $$$a ^ {n-1} \ not \ equiv 1 \ pmod n$ ，则数字n为合成。 否则， n可能是素数。 测试中使用的a值越大，则n为质数的可能性越高。

不幸的是，有一些要比较的复合数n $$$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ 与n互为素数 。 这样的数字称为卡迈克尔数字 。 成功通过Fermat测试的化合物编号称为伪简单Fermat。 伪简单费马数是无限的，因此费马测试不是确定素数的最可靠方法。

米勒-拉宾检验

结合费马小定理和以下事实，就可以得到更可靠的结果：对于素数p ，方程无其他根 $$$x ^ 2 \等效1 \ pmod p$ 1和-1除外。 Miller-Rabin测试枚举a的几个值，并检查以下条件是否成立。

令p为素数， $$$p-1 = 2 ^ SD$ ，则对于至少一个条件为true的任何一个 ：

1. $$$a ^ {d} \ equiv \ pm1 {\ pmod {p}}$
2. 有一个整数r <s使得 $$$a ^ {2 ^ {r} d} \ equiv -1 {\ pmod {p}}$

费马定理 $$$a ^ {p-1} \ equiv1 \ pmod p$ ，以及 $$$p-1 = 2 ^ SD$ 从等式的根的性质 $$$x ^ 2 \等效1 \ pmod p$ 因此，如果我们找到一个不满足其中一个条件的条件，则p是一个复合数。 如果满足其中一个条件，则根据Miller的说法，数字a被称为数字n的简单性的证明，数字n本身可能是质数。

发现简单性的见证者越多， n为素数的可能性越高。 根据拉宾定理，随机选择的数字a将见证复合数的简单性的概率约为 $$$1/4$ 。

因此，如果我们检查k个随机数a ，那么将复合数作为质数的概率 $$$\约（1/4）^ k$ 。

算法的复杂性 $$$O（k \ log ^ 3p）$ 其中k是支票数。

由于其速度快和精度高，Miller-Rabin检验被广泛用于素数搜索。 许多现代密码库在检查大量数字是否简单时仅使用此测试，而且正如马丁·阿尔布雷希特（Martin Albrecht）在他的工作中所表明的那样，这并不总是足够的。

他能够生成这样的复合数字，并成功通过了OpenSSL，CryptLib，JavaScript Big Number和其他许多库中的简单性测试。

Luke测试和Baillie – PSW测试

为了避免当攻击者生成的复合数字以素数形式出现时的相关漏洞，Martin Albrecht建议使用Baillie – PSW测试。 尽管事实上Baillie – PSW测试是概率性的，但迄今为止，尚未找到成功通过该测试的化合物编号。 为了在1980年找到一个这样的数字，算法的作者答应奖励30美元。 奖品尚未领取。

许多研究人员检查了所有数字，直到 $$$2 ^ {64}$ 而且没有一个化合物号通过了Baillie – PSW测试。 因此，对于较少的数字 $$$2 ^ {64}$ 该测试被认为是确定性的。

该测试的实质是通过两种不同的方法在停机时间一致地检查故障数量。 这些方法之一是上面已经描述的Miller-Rabin测试。 第二个是卢克对强伪简单性的检验 。

卢克强伪单纯性检验

卢克序列是重复序列对 $$$\ {U_ {n}（P，Q）\}，\ {V_ {n}（P，Q）\}$ 由表达式描述：

$$

$${\ displaystyle U_ {0}（P，Q）= 0，\ quad U_ {1}（P，Q）= 1，\ quad U_ {n + 2}（P，Q）= P \ cdot U_ {n +1}（P，Q）-Q \ cdot U_ {n}（P，Q），\，n \ geq 0}$$

$$

$${\ displaystyle V_ {0}（P，Q）= 2，\ quad V_ {1}（P，Q）= P，\ quad V_ {n + 2}（P，Q）= P \ cdot V_ {n +1}（P，Q）-Q \ cdot V_ {n}（P，Q），\，n \ geq 0}$$

让 $$$U_n（P，Q）$ 和 $$$V_n（P，Q）$ 是卢卡斯序列，其中整数P和Q满足条件 $$${\ displaystyle D = P ^ {2} -4Q \ neq 0}$

我们计算雅可比符号 ： $$$\左（{\ frac {D} {p}} \右）= \ varepsilon$ 。

找到相等的r，s $$$n-ε= 2 ^ rs$

对于素数n ，下列条件之一成立：

1. n分 $$$U_s$
2. n分 $$$V_ {2 ^ js}$ 对于一些j <r

否则， n为复数 。

对于给定的参数对P，Q，复合数n将成功通过Luc检验的概率不超过4/15。 因此，应用k次测试后，该概率为 $$$（4/15）^ k$ 。

Miller-Rabin和Luke检验分别产生不相交的伪简单数集，如果数p通过两个检验，则很简单。 Baillie – PSW测试正是基于此属性。

结论

根据任务，可以使用各种查找素数的方法。 例如，在搜索较大的梅森素数时，首先，使用Eratosthenes或Atkin的筛子，确定到一定边界的素数列表。 $$$10 ^ 8$ 。 然后，使用Luc-Lemer检验对列表中的每个数字p进行简单检查 $$$M_p = 2 ^ p-1$ 。

为了生成用于加密目的的较大质数，选择了一个随机数a并通过Miller-Rabin测试或更可靠的Baillie – PSW进行了验证。 根据素数分布定理 ，对于从1到n的随机选择的数， 素数 的几率大约相等 $$${\ frac {1} {\ ln n}}$ 。 因此，要找到1024位的质数，就足以找出大约一千个选项。

PS来源

可以在GitHub上查看所有上述算法在Go 上的实现 。