👨🏻‍🎤 🐔 😽 黄金一代 ⏪ 👨🏻‍✈️ 🙍

在继续本系列文章中开始的主题时，今天我们将讨论素数的生成。生成是概率性的，并且可以保证。因此，我们的情况是保证您可以使用在与密码相关的应用程序中获得的数字，从而确保了例如通过银行应用程序管理资金的安全性。此外，您将看到如何保证可以接收到足够大的素数以进行加密，以及如果忽略保证会出现什么问题。

用于数据交换的一般安全方案是基于分解大量复合数的复杂性。而且，如果有很多因素，那么它们将很小，并且这大大简化了安全系统的黑客攻击。因此，通过将一定大小的两个质数相乘可获得大的合成数。但是，这里有一个问题很明显-如何选择足够大的素数？

首先，确定尺寸。在现代密码学中，复合数字的顺序由以下公式确定

$2 ^ {2048}$ ，也就是说，实际顺序为2048（二进制）。此复合数的除数约为1024，即在值附近

$2 ^ {1024}$ 。为什么是1024？因为十年前已经分解了一个因数为768的因数，而今天很可能分解了1024的因数，所以出于可靠性的考虑，决定一次将该阶数加倍，即为2048。所需因素的顺序。

但是，如果因子的顺序远小于1024，会发生什么？然后，即使在大约2048的数量级内，您也可以在一个可接受的时间内分解该复合数。因此，有必要确保我们选择的因子的阶数确实接近1024并且很简单，也就是说，它们不会被分解。但是，这里的选择本身是根据概率方案进行的，这只会导致潜在的问题。

如果数字的周期（在此进行描述）是数字本身的整数除以负（即1），则在以下假设的基础上检查数字是否简单：

$N-1$ ）以公式的形式，看起来像这样：

$a ^ p \ pmod N = 1$

$N-1 \ pmod p = 0$

在这里

$N$ -调查号码，

一

$一$ -来自的价值

$2$ 之前

$N-2$ （它确定计算周期的数字系统的基础），

$p$ -调查号码的期限。运作方式

$mod$ 这里的意思是将第一个操作数除以第二个的余数。

现有的检查仅依赖于这种方法，因为对于大量检查而言，通过已知测试无条件确定简单性需要花费很长时间。但是这种检查的缺点是显而易见的-有时您可以得到一个复合数字，而不是一个简单的数字。而且，没有人知道除数将成为这个数的一部分。更准确地说，攻击者将能够通过应用众所周知的分解方法来发现问题，如果这些因素小于几百位，则该方法将在可接受的时间内开始工作。

概率简单性错误多久出现一次？很少。数以万计的简单错误有一个错误，有时甚至是两个，但没有什么可以保证我们不会犯三个错误。此外，很大程度上取决于所使用的测试。因此，例如，在BigInteger类的标准Java语言库中，实现了一种检查，该检查允许每千个简单检查丢失2-3次。也就是说，您不应该认为如果理论上几乎没有错误，那么在实践中，一切都会变成巧克力。

这有多危险？似乎并不像某些人所说的那样可怕，因为好吧，如果一个关闭使用https协议浏览其页面的站点收到了一个容易计算的密钥，那么问题将出在哪里？好吧，黑客会发现您在该站点上阅读了哪些新闻，这有什么意义？但实际上，不仅在浏览Web时会进行加密。如果黑客发现您最喜欢的银行服务的密钥以远程管理您的资金，那么将发生更不愉快的情况。再次，尽管为了确保与银行的交易安全（如果银行使用了简单性弱的支票），黑客将不得不等待大约500年，直到最终实现发布易于计算的密钥的可能性为止，因为密钥的有效期通常为1年，因此，为保证黑客入侵，您需要等到执行500次新密钥发布后才能进行。似乎所有事情都是合乎逻辑的，但还有另一个“但是”-世界上有500多家银行。因此，现在，也许在您最喜欢的银行中，黑客可以使用您自己的钱。

你害怕吗当然不会，因为我们都很勇敢，直到烤鸡啄。但是仍然有一些值得担心的地方。尽管黑客准确地对您的银行进行成功攻击的可能性并不高，但是尽管如此，如果能够实现，则可能找不到您的钱。怎么了这非常简单-银行安全服务的第一个标准假设是，应该指责拥有适当访问权限的人。不是黑客，他们也认为干扰的可能性很小，即是他们自己造成的。因此，黑客很可能不受惩罚。

如何解决这个问题？您需要学习如何获得保证的质数。但是如何保证其简单性呢？有四种方法。

第一种方法是采用最少的限制进行破坏。这通常是改进的Eratosthenes筛子的变体。该方法可靠且有保证，但仅限于非常适中的订单（少于一百个）。因此，此方法不适用于密码学。

第二种方法是具有更强限制的枚举。因此，如果数字的周期等于数字本身减去1，则可以保证该数字为质数。这里的公式是-

$N-1 = p$ 。但是，为了确定数字与单位之间的差的周期的相等性，使用了非常繁琐的方法，这些方法不适用于所有数字类别。因此，如果我们增加数量的大小，它们在密码术中的使用要么取决于有限数量的特定类，要么取决于验证过程。此外，即使是某个类别的数字本身也不能保证任何事情，这意味着需要挑选出许多候选数字。在这里，例如，已经对梅森数进行了无条件的简单性检验，发现梅森数在密码学使用的范围内实际上不存在。这是他们的全部订单，分别为1279、2203、2281、3217。如您所见，从1024到2048，只有一个合适的数字。但是，即使我们把其余的保留下来，它们的数量也很清楚地向我们暗示-这是不值得的！因此，我们再次无法通过验证方法。

第三种方法是概率性的。就是今天使用的，包括您最喜欢的银行。他如何工作？非常简单-将任意数除以幂的余数进行检查

$N-1$ 在

$N$ 如果余数是1，则数字很可能是质数。在这里，“可能”一词是最不愉快的。尽管用于检查简单性的概率方法也包含其他改进，但是，如上所述，标准Java库经常被误认为。

最后，第四种方法。它不能像概率测试那样快（尽管也可以在此处进行优化），但是即使在很容易定义的期间内，它也可以保证有素数。您问什么是黄金时期？例如，生成伪随机或加密序列。更准确地说，在知道了周期之后，我们确切地知道了序列中会有多少个数字，这使根据该数字计划使用序列生成器的时间变得容易。没错，这已经适用于对称加密，但在许多情况下也很有用。接下来，我们将考虑一种理论，该理论可确保检查候选人数的简便性。

理论背景

要了解如何生成保证质数，您需要进行一些数学运算。但是请不要惊慌，数学是五年级。

为了完整起见，建议在此处查找有关什么时期和一系列残基的详细信息。好吧，简单地说，通过将单元的“角”（任何学生都知道的一种方法）除以为研究选择的数量，就会形成许多残基。同时，在每个步骤中，较高的数字（添加了零）和所研究的数字乘以0到9（对于十进制数字系统）而言，是一个余数。但是除以“角”需要很多步骤，因此也有许多残基，它们一起形成了一系列残基，其中同一组数字被周期性地重复无限次。新周期开始的迹象是余数等于1。单位之间的残差量是周期（或周期）的长度。实际上，这只是全部，但值得一提的是，这种构造一系列余额的方法可以使用任何数字系统应用，尤其是基数为2（而不是学校习惯的10）的系统将最常用。当使用其他编号系统时，所有规则都将保留，但是每一步的产品变型数量将不同，等于b（从基数开始），即编号系统的基数。

因此，从前面显示的内容中，我们知道组合数始终给出相对较短的时间段，其中不包含多个“禁止”值。知道了复合数的因式分解后，就很容易计算出形成给定数字周期的多个残基中必须缺少多少个值。如果序列本身是基于不是任何除数的倍数的数字系统构建的，则一系列残差将不包含因数和所有这些因数的数（即，基数不除以数的除数）。例如，如果只有两个因素，则多个残差的数量由公式确定

$m = a + b-2$ 在哪里

$m$ -多个残基的数量，

$一$ 和

$b$ 是构成我们的综合数的因素。知道了“禁用”残基的数量，很容易计算出一系列残基的长度超过该值的一半

$N-1$ 长度等于

$L = N-1-（a + b-2）= N-a-b + 1$ 。也就是说，这样的系列将会

$a + b-2$ 比给定数字为质数时的序列短。这就解释了为什么所有数字都等于整个周期的数字（即

$N-1$ ），结果很简单-如果从残基序列中排除至少一个元素（“被禁止”），则期间将变短

$N-1$ 。由于存在这种规律性，我们观察了所有这些概率检验的可操作性，这些检验今天证明了数字的简单性。这些测试计算每个头寸一系列余额的值。

$N-1$ 或

$（N-1）/ 2$ ，如果值相等

$1$ 或

$N-1$ ，那么该数字很有可能是质数。为什么只以高概率而不是保证？因为期间概率测试不是计算出来的，而是位置之间的

$N-1$ 和

$（N-1）/ 2$ 可能会有更多的单位，这将意味着该期间对价值的不平等

$N-1$ 但是如果期限不相等

$N-1$ ，则数字可以是复合的。此外，缺乏平等本身并不重要，另一件事很重要-伪简单数字可以给出单位的这种安排。在通过这种测试验证的数字中，您可以找到伪合成的伪简单数字，这些数字可以帮助黑客窃取您的钱。毕竟，这些复合数的除数是多少？它们可能足够小，攻击者才能轻松打开加密的数据交换。

现在记住为什么伪素数可能会出现。此类数字的周期很短，在整个周期内会重复很多次。

$N-1$ 因此，有时他们可以在整个时期内“适应”并适应多次。因此，例如，对于以7为底的数字系统，数字25的周期为4。

$N-1$ 因为25为24，请尝试除以：24/4 = 6。即，在整个周期中将该周期布置为整数倍。可以通过上述公式来缩短周期，但是要考虑到a和b在这种情况下相同的事实。最大可能的周期将是24-4 = 20，这里24是残基总数，4是5的倍数的残基数。但是该周期并不总是最大的，所有其他选项都可以通过将最大周期完全除掉来获得。 20除以2、4、5、10，然后将20除以上面列表中的数字，我们得到的周期长度为4，这使我们在整个周期结束时

$N-1$ 单位。在检查简单性时，只检查位置上的值

$N-1$ ，即整个周期中的最后一个值。对于25，它等于1，这表示数字简单。尽管实际上是简单性的明显标志，但对于数字系统的所有基础来说，

$N$ ，则整个周期的最后一个值等于1。但是无法检查所有数字系统中是否存在大数字，因此出现了伪简单数字，有时甚至在密码学中也会使用它们，这增加了我们财务的脆弱性。

如何消除伪素数的影响？原则上讲，这很简单-您可以检查所有数字系统的周期，但是对于大量数字而言，此操作将没有足够的时间。因此，我们将走另一条路。路径也很简单（从字面意义上讲，它使用其他质数）。我们已经看到，短周期可以适合整个周期整数倍，这给了我们伪简单数。但是，是什么阻止我们采取和取消这些星期一？是的，总的来说，没有什么可以阻止。

在短期内，整个时期（

$N-1$ ）必须分为多个除数。因此，对于数字25，整个周期24分为2、3、4、6、8、12。存在许多进入伪简单数字保护区域的可能性。因此，我们只需要把一个素数作为一个完整的时期，因为它根本不会分裂成任何东西，因此会自动将我们从敌人的手中拯救出来。确实，有一个“但是”-我们需要质数，并且已知它们是奇数（除了一个例外-2），这意味着

$N-1$ 简单然后本身

$N$ 它不再是简单的了。因此，我们将不得不承认出现时期不完整的可能性。为什么这样不好？正如我们在上面看到的，整个期间保证了数字的简单性，但是我们尚未证明不完整的期间。因此，我们需要证明这一刻。

证明非常简单-复合

$N$ 时长

$N-1$ 在不是N的因数的倍数的数字系统中获得的两次残差只有两行残基，而且它们都不应该包含是N的因数的倍数的数。

$N$ （“禁止”数字）。如果从一行残基中排除了至少一个元素，那么第二个残基会自动减少相同的数量（毕竟，一行等于另一行乘以第一行中没有的任何数字）。因此，如果数字中存在除数

$N$ ，我们得到的所有“允许”余额的两个期间的总长度都比整个期间的值都短，从而在整个期间结束时将其从其位置移开，从而确保了不存在伪简单性。但是，除数余数的数量是否可以精确到整个周期的一半或三分之一？的确，那么，例如，我们将收到三分之二的“允许”余额（两行）和三分之一的“禁止”余额，总计-整个期间。但是要获得三分之一，我们需要确保整个时期的可分割性（

$N-1$ ）乘以3，我们可以很容易地排除-将质数乘以2，然后将结果加1-瞧，我们保证会排除伪简单性。与他一起，被除数可除的除数的数量不能等于整个周期的三分之一，因为他不能除以三个完整的周期。剩下的选项是余数的一半，即除数的倍数

$N$ 。消除此选项会稍微困难一些，因此下面会有一点偏离。

计算期间或所有数字-梅森的孩子

可以计算任意数量的周期。在最简单的情况下，只需将角除即可完成计算

$1 / N$ 直到我们遇到等于1的余数（在数字系统中，不是除数的倍数）

$N$ ）但是对于大量用户来说，这是不切实际的漫长的。因此，需要导出用于计算周期的公式。当我们在输入端有一个数字而在输出端有一个句点时，就存在这样的公式，尽管它不是理想的形式。公式为：

$N = \ frac {b ^ {m + n + 1} -1} {b ^ n + k}$

在这里

$N$ -调查号码，

$b$ -使用的号码系统（基础）的基础，

$m$ -最高学位

$b$ 取幂的结果较少

$N$ （换句话说，

$N$ 在数字系统中

$b$ ），

$n$ -索引中一系列残基从左到右的距离

$m + 1$ （等于

$N$ ）到一个，

$k$ 是一些整数系数。

公式输出

通过公式的定义，很明显（1）

$b ^ {m + 1} -N = x$ 即第一学位

$b$ 哪个更大

$N$ ，让您减去

$N$ 并在形式上有所不同

$x$ 。从定义也可以得出（2）

$x * b ^ n-k * N = 1$ 在这里

是整数系数。如果您将（1）乘以

$k$

并替换

$b^n$

到（2）的值，等于

$x*b^n$

，我们得到

$kN+1$

$b^{m+n+1}=N*b^n+kN+1=N*(b^n+k)+1 => N=\frac{b^{m+n+1}-1}{b^n+k}$ 。

有用的属性

我们可以看到，使用此公式，您可以获得具有已知周期的数字。确实，有一个困难-您需要选择一个系数

，对于较大的数字，又变为无法达到的目标。但是该公式为我们提供了其他内容-我们清楚地看到了所有数字是如何形成的。是的，因为所有数字都有一定的周期，所以绝对可以通过此公式获得所有正整数。有趣的是，所有数字都是通过将梅森数字除以其除数之一获得的。回想一下，梅森数是一个等于

$k$

$2^n-1$ 。在分子的公式中，我们看到具有任何基数（当然包括2）的梅森数的概括。如果我们对素数感兴趣，那么除了2以外，我们将不需要其他任何底数。

知道我们分享梅森素数，这将是能够计算数字的时期是在梅森数的分割的情况下（记得扩展概念的时期有用这里）。但是非常值得注意的是，用于计算梅森周期的公式与用于计算该类型周期的公式是一致的

$1/N$ 。那么，要导出用于划分梅森数的公式，所用的原理与得出用于划分除法公式的公式相同

，除了用于计算一系列带有索引的残差中的值的公式

$1/N$

看起来像这样-

$n$

，对于二进制数，我们得到

$\frac{b^{n+1}-1}{b-1}$

$2^{n+1}1$ 。

现在我们已经掌握了所有卡片，可以通过在素数等级中打开伪简单的弓箭手来开始游戏。

从前面的系列中我们知道，当整除后，数字的整个Mersen周期必须适合整数倍的Mersenne数字的位数。因此，在上式中，仅当分母的周期等于分子或小倍数时，整数解才可能。但是更短的时间将给我们，包括数字本身的除数

，因为

$N$

除以Mersenne数，然后除数也除以Mersenne数。这是非常重要的一点，因为由此得出除数N的周期长度除以周期的长度

$N$

完全是

也就是说，如果我们采取

$N$

是这样的，它的周期等于分子的周期，则所有除数

$N$

将同时为Mersenne数的因数，因此必须适合该周期和

$N$

和梅森数为整数倍。

$N$

再约一半的时间

现在回想一下，我们停止了寻找一种方法来证明可以排除一系列残数的一半长度是其除数的倍数的情况。我们希望证明这一点，以便在选择一个质数作为构建下一个质数周期的基础时消除伪质数。因此，现在我们知道，如果构造数具有除数，那么它们的周期始终会完全除以构造数的周期。然后剩下的工作就是检查哪些除数可以满足先前对构造数指定的限制。这样的限制-他的任期仅分为

及以上

$2$

$(N-1)/2$ 。因此，只有带句点的数字可以除数

$2$ 和

$(N-1)/2$ 。期间

有一个数字

$2$

，此期间没有其他数目更多。期间

$2$

不适合的整数倍

$2$

，因为

$(N-1)/2$

是素数，因此在此期间不包括三等分。所以只剩下一种可能性-分频器有一个周期

$(N-1)/2$

$(N-1)/2$ 。但是数字不能小于或等于其周期，因此除数的最小值为

$(N-1)/2+1$ 。如果我们将两个最小除数相乘，我们得到-

，该值必须是没有更多

$(N-1)^2/4+(N-1)+1=(N^2-2N+1+4N)/4=(N^2+2N+1)/4$

，因为我们在谈论分隔线

$N$

$N$ 。然后我们得到不等式

$(N^2+2N+1)/4\leq N => N^2-2N+1\leq 0$ 。不等式只能为负或等于零

，因此，对于以这种方式构造的所有数字，如果结果数字大于，则将排除伪简单性

$N=1$

$1$ 。好吧，对于较小的数字，我们甚至可以在头脑中测试简单性。

现在有两个选项-新数字是我们需要的质数，或者这是一个复合数字，然后其周期不适合整个周期的整数倍，因此可以通过计算完整残差系列中的最后一个值来简便地检查此数字的简便性。即，可以使用标准的概率简单性测试轻松地检查构造的数量，重要的是，测试结果不会是概率性的，但是可以保证。因此，最后，我们摆脱了伪简单性的诅咒，这给所有概率测试带来了压力。

但是，当然，如果所有问题都这么简单地解决，生命将是美好的。为了消除伪简单性，我们没有排除没有被任何人隐藏并且没有被任何东西掩盖的数字。有了它们，还有另一个问题-目前，我们只能通过提高幂然后取余数来检查残基序列中的任意项。但是这种方法很慢。更准确地说，它足够快地用于密码学中的数字，但是它不适合在家中查找大质数，因为它需要多年计算一台常规家用计算机，这不允许我们获得40万美元（如此处所示）。

然而，几乎所有的东西都准备好计算密码素数。虽然我们的老朋友仍然存在-极致主义。他问-您是否可以使用一段时间

$（N-1）/ 2$ ，什么会阻止句点的使用

$（N-1）/ 4，（N-1）/ 6，（N-1）/ 8$ 等等？事实证明，经过适当的照顾-没有什么可以阻止！

与期间相同

$（N-1）/ 2$ 在此期间

$（N-1）/ 4$ 我们可以通过将质数乘以4并加1来设置下限。然后我们保证自己免受伪简单的影响，周期小于

$（N-1）/ 4$ 。因此，仍然需要考虑周期为4、3、2（如上所示，组件不包括1）的伪简单事件的可能性。从按周期计算数字的公式可以看出，股息的周期必须等于其除数的最小公倍数，这意味着该数字的可能周期

$N$ 应该不仅适合整数倍

$N-1$ （否则将不会有伪简单性），但还包含整数个除数的周期。因此，伪质数的可能除数的数量受到严格限制。由于任何数字的期限都不能更长

$N-1$ ，然后求除数

$N$ 由于除法3给予的期限不能更长

$N / 3-1$ ，此外，我们考虑到3的周期是2。

$N / 3$ 必须是奇数，因为它是奇数

$N$ 。从上面可以得出，偶数周期N / 3-1是周期2为数3的最小公倍数，这意味着潜在的伪简单N的可能周期应等于数的周期

$N / 3$ 。总共有一个值

$N$ 对于可能的伪简单性，

$（N-1）/ 4$ 。对于其他值，

$N / 3$ 太少或其期间（以及期间）

$N$ ）将进入下面的禁区

$（N-1）/ 4$ 。奇数相同的故事，更少

$N / 3$ 但他们的时间不能更长

$（N-1）/ 4$ ，因此将它们全部排除在外。现在表明

$N / 3$ 不能有一段时间

$（N-1）/ 4$ ，这意味着它不能完全分割整个期间。首先，回顾一下公式

$m = a + b-2$ ，这为我们提供了一个只能被整数整除的数的除数残差数

$一$ 和

$b$ 。就我们而言

$N$ 应该分为

$N / 3$ 并且除以3，所有其他除数都被排除，所以我们得到-

$m = N / 3 + 3-2 = N / 3 + 1$ 。现在，您需要从整个期间减去“禁止”值，这将是

$N / 3 + 1$ ，然后除以4。我们得到了可能的工作期限

$3 * N / 3$ ：

$p =（N-1-N / 3-1）/ 4 = N / 6-1 / 2$ 那少

$（N-1）/ 4$ ，即一段长度

$（N-1）/ 4$ 不可能，因为需要考虑“禁止”残基，这将所有可能的伪简单周期带到了禁止区域（较少

$（N-1）/ 4$ ）这意味着这种情况保证了我们构造的数字不是伪简单的，因此我们可以再次确定后续概率简单性测试的结果。

同样，考虑到整个周期的可除性，对于其他值也可以得到相同的结果。但是，如果我们想以这种方式获得密码素数，然后乘以2,4,6，我们将在很长一段时间内增加数字的大小，因此，朝另一个选择的方向看是有意义的-两个素数的乘积。如果我们将一个质数乘以另一个，我们将得到一个奇数，因此我们也必须乘以2才能获得一个偶数全周期和一个奇数的质数候选。在这种情况下的整个期间将分为

$2，a，b，2a，2b，ab$ 在哪里

$一$ 和

$b$ 是素数。现在，我们需要证明所指示的时间段不会给出伪简单性，或者要找到警告我们伪存在的迹象。请注意，如果周期等于

$2 * a * b$ ，那么数字将是质数（如上所示）。上面还显示，半周期数不能是伪简单的，因此长度为

$ab$ 可以排除。虽然为了完整性，您可以检查期间

$ab$ 替代方式。所以如果时期是

$ab$ ，那么

$一$ 和

$b$ 很简单，显然除数周期的最小公倍数

$N$ 只能相等

$ab$ ，而分频器的周期可以等于

$ab$ 两者或一个

$一$ 还有一个

$b$ 。由于周期始终小于数字本身，因此

$（ab + x）*（ab + y）$ 显然会有更多

$2ab + 1$ 。因此，在这样的时间段内不可能实现伪简单性。因此，仍然需要检查期间

$2，a，b，2a，2b$ 。 2小于所有数字的最小可能期限，大于3，因此我们排除了该期限。现在假设构造数除以

$m$ 和

$n$ ，然后等于时期

$N$ 意思

$一$ ，他们的期间也将相等

$一$ ，因为这是两个数字的唯一最小公倍数，因为

$一$ 不分任何东西。因此

$（a + x）*（a + y）= N = ab * 2 + 1$ 在哪里

$a + x = m$ -第一个可能的时期

$一$ 和

$a + y = n$ -第二。下一个：

$a ^ 2 + ax + ay + xy = 2ab +1$

$=>$

$a ^ 2 + ax + ay +（ka + r）= 2ab +1$

$=>$

$a + x + y + k =（2ab + 1-r）/ a$ 。在这里

只能等于1，否则整数在左边将不起作用。然后：

$x + y + k = 2b-a$ ，由此得出的结论是

$a \ geq 2b$ ，然后是带有句点的伪简单

$一$ 不能。仍然需要验证伪简单性

$a <2b$ ，这可以通过检查位置上一系列残差中的值来完成

$一$ 如果为1，则该数字可以是伪简单的，应将其从后续操作中排除。推理

$b$ 完全类似，这意味着需要验证单元及其剩余部分的相等性，前提是

$b <2a$ 。

期间

$2a$ 我们有：

$4a ^ 2 + 2ax + 2ay + xy = 2ab + 1$

$=>$

$4a ^ 2 + 2ax + 2ay +（ka + r）= 2ab +1$

$=>$

$4a + 2x + 2y + k =（2ab + 1-r）/ a$

$=>$

$2x + 2y + k = 2b-4a$ 。我们得到的

$4a \ geq 2b$ （或等效地-

$2a \ geq b$ ），再简单不过了，但是如果

$2a <b$ ，那么您需要检查头寸余额

$2a$ 。同样的

$b$ -检查是否

$2b <a$ 。总共，我们获得

$一$ 和为

$b$ 只需要检查订单项

$2a$ 和

$2b$ 因为时期

$一$ 和

$b$ 将重复就位

$2a$ 和

$2b$ 。仅在上述条件下执行验证，这将在检查大值时使处理过程几乎翻倍

$一$ 或

$b$ ，因为他们必须

$a \ geq 2b$ 使用下面的简单生成方案，由于其较小的值，将很快检查较低的值。

因此，上面已经显示了能够为诸如加密之类的关键区域生成保证质数的理论基础。

此外，打开了一种检查任意数的简单性的方法，只要找到其整个周期的除数（

$N-1$ ）因此，对于<126,000,000的素数，属于该类的“乘数素数”为676625，素数总数为7163812，这使我们少了9.5％。对于不超过10亿的素数，我们拥有3.49％的2p + 1类，1.8116％的4p + 1类，2.4709％的6p + 1类，只有7.7746％，其中p是素数。没错，应该指出的是，整个时期的大量分解非常困难。在这种情况下，您可以提供递归检查，这将稍微增加可用于检查的数字的大小，但同时会大大减少通过此检查的数字的比例，因为如果确定递归素数类的成员的系数等于0.2，则已经在第二次检查中仅具有0.04或素数总数的4％。但是，在某些情况下，这种方法可能是有益的。

实际结果

当然，生成器本身是经过编写和测试的，因为其中的复杂性极低。在检查过程中，发现以下算法将完全起作用：

例如，我们得到了1000个初始素数，可以使用Eratosthenes的筛子生成它，也可以直接从此处下载。然后，我们将每个值与每个剩余值相乘，并且不要忘记将其乘以2，然后加一。所得的候选数通常被3除，因为质数具有类似于物理学中粒子上存在电荷的特定特征。具有相同“收费”的简单人被排斥，而具有不同“收费”的人被吸引。在这种情况下，“费用”是除以3的余数。也就是说，如果两个素数的除以3的余数相同，则新质数将不起作用，因为它将被3除。如果余数不同，则可以得到正确的一个简单的候选人。而且，所有通过乘法得到的简单的都是“同步的”，也就是说，它们得到等于2的相同余数。因此，再次将它们自己相乘是没有用的。因此，要获得新的质数，我们需要滤除三元组的模数（除以3的余数）为1的初始1000的那部分。因此，在所有人与所有人进行第一次乘法之后，我们长大了已经无意义的数字可以彼此相乘因此，为了进一步增加大小（达到密码术中使用的大小），我们必须一次又一次地将获得的素数乘以先前选择的“相反电荷”数。在乘以一个单位后，我们根据伪伪可能性的准则进行检查，如果满足该准则，则我们检查每个候选者在位置2a的余数。如果为1，则候选人被拒绝。接下来，通过通常的概率检验来检查每个候选者，即，以该位置的一系列残差来计算值

$（N-1）/ 2$ 如果是1或

$N-1$ ，那么我们前面就是有保证的素数。

在执行生成时，应记住，在每次迭代中，生成的素数的数量都会增加，即1000个初始素数的乘法系数远大于1。因此，要获得加密素数，必须限制生成，否则将花费很长时间，并且可能没有足够的内存。同时，不应减少一组简单的初始值，因为生成应尽可能地随机，因此，在知道其算法的情况下，攻击者将无法预测结果值。为此，有必要实现一种用于切断生成树的分支的机制，该机制每次都允许获得与先前生成的树相距很远的唯一简单树。当然，消除多余的部分可以大大加快这一过程。

测试执行时间取决于生成的候选数。每个候选人都通过了概率测试，这最大程度地减慢了生成速度。在试运行中获得几百个简单的范围

$2 ^ {900}$ --

$2 ^ {1200}$ 花了5至20分钟。该时间差通过算法在生成树中经历的各种方式来解释。因此，最初，生成限制为大约10个数字，但是随着密码大小的临近，由于乘法系数随数量的增加而显着降低，因此生成逐渐减弱。因此，有必要增加中间素数的数量，但是很难说具体程度如何，因此使用允许数量的简单增加两倍来限制数量增加和粗略阈值的增加。结果，在限制的范围内，新的简单对象的数量可能会浮动，从而在总生成时间上产生重大差异。

以下是生成素数的Java过程的文本。自然，它不能满足远远超出程序代码且主要与组织问题有关的加密要求。在纯软件部分中，除了最简单的限制外，该过程未实现用于修剪生成树分支的机制。不过，作为生成算法实现的示例，该程序可以提供一些帮助。

输入参数是用于将结果保存到文件的simple和PrintWriter的初始列表。算法完成后，文件将包含生成的素数的所有乘积，其初始编号的模块数为3等于1。可以使用实现数字分解的在线服务来检查结果，但是应该理解，为了进行分解之前它们可以使用概率测试来简化操作，因此，为了检查所提出的方法，它们变得无用（因为所有数字都已经通过概率测试进行了检验）。但是其中许多人立即开始将建议的数量因素考虑在内，这样的站点可以为建议的方法的正确性注入更多的信心。

public static void generatePrimes(List<Integer> primes, PrintWriter pw) { List<BigInteger> mod3_1 = new ArrayList<BigInteger>(); List<BigInteger> l = new ArrayList<BigInteger>(); BigInteger three=BigInteger.valueOf(3), two=BigInteger.valueOf(2); for (int k=0;k<primes.size()-1;k++) { BigInteger seed=BigInteger.valueOf(primes.get(k)); BigInteger s2=seed.shiftLeft(1); BigInteger r0=seed.remainder(three); if (r0.intValue()==1) mod3_1.add(seed); for (int i=k+1;i<primes.size();i++) { BigInteger p=BigInteger.valueOf(primes.get(i)); BigInteger r=p.remainder(three); if (r.intValue()==r0.intValue()) continue; // divisible by 3 else addIfPrime(p,seed,s2,two,l); } } List<BigInteger> ps=l; do { System.out.println("found "+l.size()+", bits="+l.get(0).bitLength()); l=new ArrayList<BigInteger>(); for (int k=0;k<ps.size();k++) { BigInteger seed=ps.get(k); BigInteger s2=seed.shiftLeft(1); for (int i=0;i<mod3_1.size();i++) addIfPrime(mod3_1.get(i),seed,s2,two,l); int n=100000; // change following to adjust for required bit count if (l.size()>0) if (l.get(0).bitLength()<700) n=10; else if (l.get(0).bitLength()<800) n=20; else if (l.get(0).bitLength()<900) n=40; if (l.size()>n) break; } ps=l; for (int i=0;i<l.size();i++) pw.println(l.get(i)); pw.flush(); } while (l.size()>0); System.out.println("Done"); } private static void addIfPrime(BigInteger a, BigInteger b, BigInteger b2, BigInteger two, List<BigInteger> l) { BigInteger a2=a.shiftLeft(1), fp=b.multiply(a2), n=fp.add(BigInteger.ONE); BigInteger r=null; if (a2.compareTo(b)<0) r=two.modPow(a2,n); // 2a<b else if (a.compareTo(b2)<0) r=two.modPow(a,n); // a<2b if (r!=null && r.compareTo(BigInteger.ONE)==0) return; r=null; if (b2.compareTo(a)<0) r=two.modPow(b2,n); // 2b<a else if (b.compareTo(a2)<0) r=two.modPow(b,n); // b<2a if (r!=null && r.compareTo(BigInteger.ONE)==0) return; r=two.modPow(fp.shiftRight(1),n); if (r.compareTo(BigInteger.ONE)!=0) return; l.add(n); }

好吧，既然您（几乎）几乎了解生成质数的一切，也许您的兴趣将不仅限于密码学，而且对数论的研究也将变得很有趣，因为如上所述，五年级学生可以使用它，但同时，它也使您可以独立寻找真正的钻石，而无需等待认真的数学家的帮助。

黄金一代

理论背景

计算期间或所有数字-梅森的孩子

公式输出

有用的属性

再约一半的时间

实际结果

More articles: