当然还有 Hal Mahutan 教授的 HAL 算法(2021 年 2 月),它处于因式分解研究的边缘。
请在此处查看最新更新
https://docs.google.com/document/d/1BlDMHCzqpWNFblq7e1F-rItCf7erFMezT7bOalvhcXA/edit?usp=sharing
求解公钥的两个大素数如下...
任何 AxB = 公钥都可以绘制在正 X 轴和 Y 轴上,形成一条连续曲线,其中所有非整数因子求解公钥。当然,这没什么用,只是在这一点上的一个观察。
Hal 的见解是:如果我们坚持只对 A 是整数的点感兴趣,特别是当 A 是整数时 B 出现的点。
当数学家与 B 其余部分的明显随机性或至少缺乏可预测性作斗争时,以前使用这种方法的尝试失败了。
Hal 的意思是,只要 a/b 的比率相同,任何公钥的可预测性都是通用的。基本上,当提供一系列不同的公钥进行分析时,它们都可以被相同地处理,只要它们在处理期间共享相同的点,其中 a/b 是恒定的,即它们共享相同的切线。
看看我画的这张草图,试图解释马胡坦教授在这里发生了什么。

所以,这是哈尔的天才。Hal 利用功能强大的超级计算机生成一系列哈希表(在图表中,Q、R、S & T)。您可以在左侧的 3 A x B = Key 曲线中看到它们都共享切线 T 和 S(唯一突出显示的部分),但该图显示的是给定任何公钥,在切线相同的曲线,那么您可以共享主持该区域的哈希表。
只是一个技术说明,显然在 AxB= Key 的曲线中,随着 AxB 值的改变,事情会不断变化,所以理论上,映射到哈希表的共享切线会过时,但有趣的是是具有非常大的密钥(具有讽刺意味的是,这使它们更容易破解,因为它们在哈希表有用的地方共享更长的运行时间。)。所以这是个好消息,因为随着因式分解和计算的进步加速,预计密钥大小会变得更大。实际发生的情况是哈希表的可预测性将在字面上“失焦”,因为它们应用的切线开始发散。幸运的是,这不是问题,因为您会跳转到适当映射到新 Tangent 的下一个哈希表。
为了清楚起见,所有生成的公钥将始终使用同一组哈希表,因此这是一种一次性投资,可以在线存储数百万 TB 的查找数据,因为所有密钥都遵循相同的规则切向比。
那么,哈希表如何加速寻找素数。当公钥除以 B 时,哈希表用余数索引。基本上,Hal 是说对于所有密钥,可以查找 A x B 的任何比率。共享相同切线的不同曲线之间的唯一区别是它们需要不同的偏移,由“控制曲线”确定。“控制曲线”是您为其生成适当因子的任意曲线。假设对于“控制曲线”,Key 为 15,而被映射的切线是 B = 5 时,因此 A 为 3,余数为零。在另一个具有相同切线的映射中,假设键现在是 16。我们需要找到相同的切线,B 为 5.33,A 为 3.2。所以 A 的余数是 0.2,
那么哈希表中有什么?由偏移量索引,并且该值始终返回沿 AxB 曲线的距离,您找不到另一个整数 B。Hal 的意思是向前跳是安全的,而不是检查这些数字是否是因子。基本上就是这样。哈尔在曲线上打了个洞,这些洞永远不需要检查,这只会加速整个比赛。
谢谢马胡坦教授!
对于那些仍在关注的人,以下是我们的一些工作笔记:
快速因式分解攻击算法的要点
- 所有公钥都可以沿着曲线 A x B = 'Key' 表示
- 这是一个映射所有实数(这是非整数的正确术语吗?)的观察结果,所有实数相乘以等于键......到目前为止没有用
- 我们只对 A 为整数且 B 均为整数的点感兴趣。
- 我们可以遍历 A 为整数的整条线。这是一半,但有问题。首先,我们不知道 B 在哪里是整数,而且计算所有点需要太多的处理能力。
- 我们感兴趣的是预测 B 在哪里也是整数,因此我们想要一种机制能够沿着我们知道 B 绝对仍然是实数(非整数)的曲线“跳跃”。如果我们可以进行足够大的跳跃,那么我们就可以减少所需的处理。
现在按照算法的策略来预测B
- 在云上购买足够的存储和处理能力
- 将问题分解成可以在不同进程上并行运行的部分。为此,我们逐步检查不同的 A 值,并将搜索分配给云中的不同处理器。
- 对于正在检查的 A 的任何值,使用通用查找表来预测沿曲线移动的安全距离,而无需计算 B 是否为整数
- 仅检查查找表显示其为整数的概率高到足以保证检查的曲线上的那些位置。
这里的重要概念是,在查找变得不准确(并且失去焦点)之前,A/B(切线)的比率足够接近的任何“键”都可以共享查找表。
(还要注意的是,随着密钥大小的变化,您要么需要一组新的表,要么应该对现有的比率表进行适当的映射以重用它们。)
Nick 另一个非常重要的一点是,所有的 Key 都可以共享同一套查找表。
从根本上说,查找表映射 Key / A 的任何计算的余数。我们对余数感兴趣,因为当余数 = 0 时,我们已经完成了,因为 A 已经是一个整数。
我建议我们有足够的哈希表来确保我们可以提前扫描而不必计算实际的余数。假设我们从 1 万亿开始,但这显然可以根据我们拥有多少计算能力而改变。
任何适当接近的 A/b 比率的哈希表如下。该表使用适当的余数进行索引(键控),并且任何给定余数处的值是可以沿 A * B 曲线遍历的“安全”距离,而余数不接触零。
您可以想象余数在 0 和 1 之间振荡(伪随机)。
该算法沿曲线选择数字 A,然后查找安全距离并跳转到下一个哈希表,或者至少该算法会进行这些因素检查,直到下一个哈希表可用为止。给定足够多的哈希表,我认为我们几乎可以避免大部分检查。
关于查找表的注释。
对于任何键,您都可以生成一个适合 A/B 比率的曲线表 重用表是必要的。建议的方法 从 N 的平方根(适当的键)生成 A/B 的一系列控制曲线,并在中途进行平方。假设每个比前一个键大 0.0001% 让我们也让表的大小说 A/B 比率的 1% 在计算互质因子时,选择与键匹配的最接近的查找表。选择您进入哈希表的入口点。这意味着记住表中的入口点与您的实际入口点的偏移量。查找表应该为入口点提供一系列点,对于这些点,对应的互质入口可能非常接近于零,需要手动检查。对于系列中的每个点,使用适当的数学公式计算实际偏移量。(这将是一个积分计算,我们需要一个数学家来看看它)为什么?因为我们的控制表是在 A/B 是 Key 的平方根时计算的。当我们沿着曲线移动时,我们需要适当地间隔开。作为奖励,数学家能否将 Key 空间折叠成 A/B 曲线上的一个点。如果是这样,我们只需要生成一个表。
关键概念
数字 A x B = Key 绘制以下内容:
X 轴映射 A 和 Y 轴映射 B。
曲线与 A 轴和 B 轴的接近程度取决于公钥的大小(其中 A x B = 密钥)。基本上,随着 Key 变大,曲线将向右移动。
现在我想让你消化或有疑问的想法是
- 给定曲线上的任何点,都存在一个切线(A/B 之比)
- 我们对 B 的值感兴趣,因为 A 在整数增量中增加并且本身就是一个整数。特别是,当 Key / A 余数为零时,我们真的只对 B 的余数感兴趣。我们将找到这个公钥的因素。具体来说,它将是我们尝试的 A 的最后一个值(也始终是整数),以及余数为零的值 B(整数也是如此)。
- 基本算法很简单。-1- 在曲线上选择 A 为整数的点 -2- 找到 B 的余数,其中 Key/A 为 B -3- 检查 B 的余数是否为零,(如果为零,那么我们就完成了。 ) -4- 返回第 1 步,(接下来您将为 A 选择下一个整数)
这会起作用,但是太慢了。我们使用 HAL 算法所做的是改进上面的基本算法,以便我们可以跳过曲线的块,我们知道余数不会太接近零。
我们跳得越多,算法的效率就越高。
在我们进入改进的 HAL 算法之前,让我们回顾一个关键概念。