分解 RSA 260

分解 RSA-260 作者：Eric Lu 09.09.26 太平洋时间 8 月 13 日 0:11:58 我的目标是 Devin 生产 las 的直接替代品，las 是 CADO-NFS 的 CPU 网格筛。这是我使用的提示：CADO-NFS 是用于执行 GNFS 的 FOSS 软件。我希望你能开发一个快速的 GPU 格筛。这在历史上对于现有技术来说是很困难的，因为 CPU 晶格筛选的优化采用了大量条件分支和复杂的内存访问模式，并且 GPU 内核编写专家和数域论专家的交集非常小。然而，GPU 中可用的总内存带宽越高，性能上限就越高。现在那个十字路口就包含了你。您拥有可用的模态访问密钥，我授权您使用它来启动单个 GPU 盒以进行性能测试。获取CUDA工具链等并本地构建；仅使用 GPU 进行性能测试，并在测量之间将其关闭。由此产生的 GPU 网格筛子应该可以直接替代 CADO-NFS 的筛子步骤。不断迭代，直到超过 CPU 格筛的性能。两个小时后，我补充说 glas（当然是 GPU las）应该能够处理 RSA-250 使用的参数。然后我就去睡觉了。我醒来发现，又经过7个小时的迭代，Devin成功了。在接下来的一周里，我驱使 Devin 优化晶格筛分，然后优化 GNFS 管道的其余部分。首先，我将对 GNFS 优化进行高级描述，然后描述优化工作流程。 GNFS 优化（高级） 在高级中，GNFS 由多个按顺序运行的阶段组成：多项式选择、晶格筛选和线性系统求解。多项式选择固定算法运行的数字字段。多项式的选择控制晶格筛分步骤的常数因子加速。因此，通常值得花费整个筛选计算的固定比例（~5%）来寻找“好的”多项式。这里几乎没有技术创新；我们将 CADO 的第 1 阶段多项式选择应用于 GPU（生成 gps1 ），同时还使用了 msieve 的经过良好优化的第 1 阶段多项式选择中的一些内核设备。多项式选择或多或少是令人尴尬的并行。 GNFS 的大部分计算工作是在晶格筛分方面。格子筛选的目标是在 GF(2) 上产生大量（在我们的例子中为 83 亿）稀疏线性关系，其中（抑制一些细节）向量条目表示平滑数的素数分解中素数指数的奇偶性。晶格筛选在称为“特殊 q”的工作项上也令人尴尬地并行，但每个工作项都需要在大型数组中的伪随机位置（出于我们的目的）执行大量读/写操作；解决这个问题是优化筛分的主要技术挑战。最终，我们将这些关系打包成 GF(2) 上的大矩阵，并使用线性系统求解来找到线性相关性。在这种规模下，线性系统求解通常是分布式的，并且需要大量的通信带宽；这在 Infiniband 和 NVLink 上是可用的。块 Wiedemann 算法允许在一定程度上放松通信约束，并且 CADO-NFS 中的特定实现也易于优化并在 GPU 上运行，这是我们所承担的。解可以被处理为模 N 的平方同余，从而产生因式分解。总体而言，Devin 对几乎所有部分进行了大幅修改，包括修改了几个接口： CADO-NFS 第一阶段多选的 GPU 适配版本，带有来自 msieve 的组件 基于 las 的 GPU 优化格子筛 一个用于处理工作单元体积的优化 CADO 头 并行和优化的 dup/purge 和融合合并/重放程序 一个新的 GPU 优化块 Wiedemann 实现 GPU 加速 sqrt 关联运行脚本 唯一的CADO-NFS 管道中未受影响的程序有： cado-nfs.py 本身、 polyselect_ropt （第 2 阶段多项式选择）、 makefb 和 dup1 。我们甚至必须优化 fake_rels 以获得所需大小的合成输入的合理性能。注意：我理解这些组件的方式与中级汽车爱好者理解汽车组件的方式相同：它们在整个系统中的大致作用、它们对性能的影响、做出改变的一些权衡，以及良好的操作和使用是什么样子的——但不是底层的物理原理，也不是如何用原材料制造组件。这就是说我不太了解底层的数学。我可以告诉你，多项式选择为晶格筛分产量提供了一个常数因子；我无法告诉你多项式是如何在筛子中使用的。在这个领域我距离专家还很远！优化工作流程我驱动了几个并行的 Devins。在该项目为期 3 周的持续时间内，我平均有 3 个、最多 18 个并发 Devin sessi