分解大数的新概率方法
两个大质数的乘积是许多加密算法的核心，因为对于具有几百个数字的数字而言，很难对乘积进行分解。这两个主要因素与加密密钥（公用密钥和专用密钥）相关联。在这里，我们描述了一种分解大数的新方法，该方法是两个大小几乎相同的素数的乘积。它专门用于处理此问题并识别加密算法中的缺陷。  
乍一看，它似乎大大降低了传统保理的计算复杂度，但在现阶段，要使新算法高效，仍需要大量改进。一个有趣的特征是，成功取决于两个数是互素数的可能性，因为两个数不作为共同除数共享前几个素数（例如2、3、5、7、11、13） 。可以显式计算该概率，约为99％。
该方法在很大程度上依赖于等价解系统，中国余数定理以及一些精心选择的整数的模乘逆。我们还将讨论计算复杂性问题。最后，此处介绍的另类教材会为学生学习概率，计算机科学或数论提供许多原始练习或考试题：证明我的文章中的各种简单陈述。
1.用简单的英语解释一些数论
您可以跳过本节。在这里，我概述了用于得出下一部分主要结果的理论。该水平仅勉强高于高中（1.2节除外），但即使在许多大学数学课程中也通常不教授。
1.1。互素和成对互素。第一个概念是互质数。如果两个数字不共享一个共同的因数（例如15和14），则它们是互质的。如果两个数字都不共享一个共同的因数，例如，3、4和7，则它们是成对的互质数。相反，3、4和6是互质的（没有共同的因数），但不是成对的互质的，因为3和6共有共同的因数。
1.2。成为同质的概率。如果p和q是素数，则对于一个数值的概率是通过整除p是独立于被整除q。对于两个要互质的数，它们最不共享任何质数，因此概率等于
其中乘积在所有素数上，并且ζ  是Rienman zeta函数。有关更严格的证明，请参见此处。同样，k个随机数是互质的（尽管不一定是成对的互质）的概率为1 /  ζ（k）。有关详细信息，请参见此处。k个随机数成对互质的概率为
同样，该产品适用于所有质数。当k = 2时，两个公式相同。一个证明可以在这里找到。
1.3。模乘逆。对于b   <   c的正整数，符号a = b Mod c表示| |。a - b | 除c。所述模反元素的一个   （模?）是正整数d满足广告 = 1个国防部?和  d   <   ?。当且仅当a和d为互质时，它存在并且是唯一的。  
1.4。中文余数定理，A版。
这个基本结果是中国余数定理的结果。
如果?不是素数，则下列系统?同余，与XY   ≤ ?，唯一地确定两个非平凡号码X，?使得XY = ?。换句话说，它可以让你找到两个因素X，?的?。系统如下：
这里  p 1，...，p k必须是成对的互质，并且它们的乘积必须大于z。
1.5。中国剩余定理，B版。
这是中国余数定理的一个特例，在我们的上下文中也很有用。
令p 1，...，p k   为k个成对的互质数正整数，而a > 0为整数。如果? = 一个国防部p 我为我 = 1，?，?，然后? = 一个 MOD（p 1 p 2 ?p ?）。
有关更多信息，请参见此处。
2.新的分解因数算法
基本思想是用接受更多解的同余系统代替求解xy = z的难题  （假设x和y是两个大质数），从而更容易解决。但是，到目前为止，尚未找到解决这些一致性的有效方法。  
2.1。提高计算复杂度
实际上，xy = z可以看作是一个全等式，即xy = m Mod z，其中m =0。因此，分解因数z的问题被视为求解等式的一种特殊情况，其中残差 m等于0，并且模等于z。让我们假设对于某些函数f，解决该一致性的计算复杂度为O（f（z））。计算复杂度是z的函数（因为z变大），但被认为独立于m。使用效率最低的算法，我们将得到f（z）= SQRT（z）。如果我们设法将这种一致性分解为（例如）两个较小的模，每个模的模数接近SQRT（z），那么我们会将计算复杂度从O（f（z（）））降低到  O（f（SQRT（z）） ）。并且这可以递归地进行，直到我们得出全都具有较小模数的全等。这是支配我们方法的基本原则。   
在第3节底部的练习2中讨论了有关计算复杂性的更多信息。
2.2。五步算法
为了说明该算法的工作原理，让我们将其应用于一个非常适中的数字z = xy = 1223×2731。它涉及以下步骤。
步骤1。计算f（p）= z Mod p，其中p = 2，3，5，7，9，9，11，13，...，M。上限  M将在后面讨论；与z相比，它是一个非常小的数字。检查p的值，生成许多??相同的f（p）值。在此，例如，f（p）＝ 5或f（p）＝ 23。
第二步。我们有f（59）= f（85）= f（111）=23。根据定理B（请参阅第1.5节），我们也有f（59×85×111）=23。我不确定是否这有什么帮助。
第三步。发现该组对（X，?）与X   <   ?，与X，?奇数和XY ≤ ?满足以下所有：
xy = 23模59
xy = 23模85
xy = 23模111
您需要创建3个乘法表来标识候选的完整列表（3个无限列表的交集），并忽略那些导致xy > z或x偶数或y偶数的（x，y）。
第四步。结果为（x，y）∈{（（61，36503），（173，12871），（211，10553），（829，1327），（1223，2731）}。下面的代码显示了这些对的产生方式。代码中的％符号表示取模运算符。
步骤5。在上述所有5个候选者中，检查一个是否得出xy = z。在这里（x = 1223，y = 2731）可以，并且我们已经将z分解。
如何确定M？您希望M尽可能小，但要足够大，以使您有足够低的p且具有相同的f（p）-在我们的例子中，p = 59，p = 85和p = 111-并且其乘积与z的数量级相同。  
如果相反，我们认为5个全等而不是3个
xy = 5模组21
xy = 5模47
xy = 23模59
xy = 23模85
xy = 23模111
那么在步骤4中将只有一个候选项，导致z分解。请注意，乘积21×47×59×85×111 = 549
另一个产生单个候选人（正确候选人）的示例是
xy = 2 Mod 3
xy = 3模5
xy = 5 Mod 7
xy = 6 Mod 11
xy = 1 Mod 13
xy = 6 Mod 17
xy = 3 Mod 19
同样，步骤4中只有一个候选项（因此没有步骤5），因为3×5×7×...×19 = 4
2.3。概率优化
在这里，我讨论了选择同余的另一种方法。让我们继续使用相同的示例：z = xy = 1223×2731。取两个互质本底  模数p 1，p 2非常接近SQRT（z），它也可以工作。例如，对于p 1 = 1827，p 2 = 1829，我们有：
xy = 257 Mod 1827
xy = 259 Mod 1829
对此只有一个解决方案，它是x = 1223，y = 2731，揭示了z的两个因子。之所以在这里工作，是因为1827年和1829年是偶然的。为了增加成功的机会，这两个模量是互质数，可以选择  p 1 = 2?3?5?7? q 1 + 1和p 2 = 11?13? q 2 + 2，其中q 1，q 2是尽可能地小尚未满足p 1 ? p 2 > ?。这里q 1 = 9和q 2= 13次工作，得出p 1 = 1891和p 2 = 1861。同样，这会导致在步骤4中产生唯一的（正确的）解决方案。通过构造，我们知道p 1，p 2不共享2、3、5、7、11、13作为共同除数中的任何一个，从而使除数更多它们很可能是互质的（确实如此）。在这种情况下，x，y满足
xy = 507 Mod 1891
xy = 1379 Mod 1861
用唯一的解决办法X ? ? ≤ ?和X   <   ?是再次X = 1223，? = 2731同样，X ? y = ?。两个不共享2、3、5、7、11、13的数作为共同除数的共质数的概率为
参见1.2节。产品仅在素数以上。相反，在没有上述限制的情况下两个随机数是互质的概率约为61％。当使用互素数模时，适用定理A，从而保证了唯一解（请参阅第1.4节。）最后两个等式（xy = 507 Mod 1891与xy = 1379 Mod 1861 相结合  ）被认为可以显着降低计算的复杂度。分解z的最初问题，即找到x，y使得xy = 0 Mod3340013。这两个问题是等效的。注意z = 3340013。
代替使用接近SQRT（z）的两个互质数，可以使用四个接近z ^（1/4）的成对互质数，例如：
xy = 30 Mod 41
xy = 31 Mod 43
xy = 23模45
xy = 5模47
借助第1.4节中的定理A，这也有效。效率更高吗？
3.问题的紧凑表述
让我们专注于案件? = XY与
xy  =  m 1 Mod p 1
xy  =  m 2 Mod p 2
这里p 1，p 2是互质数，和p 1 ? p 2 >?。我们进一步假设?是两个大素数的产物，并且p 1 ≈ p 2 ≈SQRT（?），从而使X <分钟（p 1，p 2）。
上面的z = 3340013，p 1 = 1891，p 2 = 1861的示例是满足这些要求的典型情况。如前所述，结果为m 1 = 507，m 2 =1379。解为x = 1223，y =2731。下面的方法以该示例为例。
让我们表示为G ^ p（Y）的模反元素?，模p，在部分1.3.That描述，G ^ p（Y由0 <）唯一地定义   ? p（Y）<   p和? ? ? p（y）= 1 Mod p。当且仅当y和p为互质时，该逆存在。可以使用扩展的欧几里得算法进行计算  。然后上面的系统有两个变量x，y和两个等式xy = m 1 Mod p 1，  xy = m 2 Mod p 2简化为一个具有一个变量（未知）y的方程，如下所示：
这是严格的相等，不是“模数相等”。最大的挑战是如何有效地求解该方程。在这里，我们证明该方程对于我们的示例是正确的。如果  p 1 = 1891，  p 2 = 1861，  y  = 2731，则我们有G p 1（y）= 1416和G p 2（y）= 1538。
507?1416Mod 1891 = 1223 = 1379?1538Mod 1861。
因此，该方程式成立。注意1223 = x，z的另一个因子  。总是这样。此外，如果你知道? p 1（Y），则可以很容易地检索  y通过执行另一个模逆：  Y = g ^ p 1（g ^ p 1（Y））+ ? ? p 1其中  ? > 0是小的整数假设  X，y彼此相对靠近。在我们的例子中，G p 1（G p1（y））= G p 1（1416）= 840并且  n = 1，得出  y = 840 + 1891 =2731。同样，如果您知道G p 2（y），则也可以检索  y。
练习题
[1]找出所有x，y，使xy = 3 Mod 7。
x = 1 Mod 7和y = 3 Mod 7，或
x = 2 Mod 7和y = 5 Mod 7，或
x = 3 Mod 7和y = 1 Mod 7，或
x = 4 Mod 7和y = 6 Mod 7，或
x = 5 Mod 7和y = 2 Mod 7，或
x = 6 Mod 7和y = 4 Mod 7。
[2]求解xy = m Mod p等式需要计算模乘表 modulo p，即（p -1）^ 2运算，请参见练习[1]。如果您需要用k个成对的互质模数p 1，...，p k求解k个这样的方程，则操作数为
比较本文研究的以下3种情况的操作数量：
p 1 = 1891，p 2 = 1861
p 1 = 41，p 2 = 43，p 3 = 45，p 4 = 47
p 1 = 3，p 2 = 5，p 3 = 7，p 4 = 11，p 5 = 13，p 6 = 17，p 7 = 19
现在是一个难题。如果我们为模选择k个最小质数p 1，  p 2，...，   p k  ，使得它们的乘积几乎不大于z，则随着z越来越大，需要渐近地进行多少次运算？解决方案：操作数的增长速度比A（log z）^ B慢，其中A，B是两个常数，其中B低至3，甚至低至2.75。
为了正确理解这一点，要将所有正整数分解为10 ^ 300，您只需执行2 x 10 ^ 7运算即可生成所有必要的模块化乘法表。然后，对于每个表（例如p），您只需要存储p -1个数据点（请参阅练习1，其中p = 7），因此所需的总存储量约为42

关注 CDA人工智能学院 ，回复“录播”获取更多人工智能精选直播视频！