theory - 使用特制的 CPU 查找大数的质因数

Question

我的理解是，如今许多公钥加密算法都依赖于大素数来组成 key ，而且很难分解两个素数的乘积，这使得加密难以破解。我还认为，分解如此大的数字如此困难的原因之一是所用数字的庞大规模意味着没有 CPU 可以有效地处理这些数字，因为我们的 32 位和 64 位 CPU 无法匹敌对于 1024、2048 甚至 4096 位数字。必须使用专门的大整数数学库来处理这些数字，而这些库本身就很慢，因为 CPU 一次只能容纳(和处理)小块(如 32 或 64 位)。

所以...

为什么你不能构建一个具有 2048 位寄存器和巨大算术电路的高度特化的定制芯片，就像我们从 8 位到 16 位扩展到 32 到 64 位 CPU 一样，只是构建一个大很多？该芯片不需要传统 CPU 上的大部分电路，毕竟它不需要处理诸如虚拟内存、多线程或 I/O 之类的事情。它甚至不需要是支持存储指令的通用处理器。只是对大量数字执行必要的算术计算的最低要求。

我对 IC 设计知之甚少，但我确实记得学习过逻辑门的工作原理，如何构建半加器、全加器，然后将一堆加法器链接在一起进行多位运算。只是扩大规模。很多。

现在，我相当肯定有一个很好的理由(或 17 个)上述方法行不通(因为其他比我更聪明的人中的一个已经做到了)但我很想知道为什么它不会工作。

(注意:这个问题可能需要重新处理，因为我什至不确定这个问题是否有意义)

Answer 1

@cube 所说的，以及一个巨大的算术逻辑单元需要更多时间来稳定逻辑信号的事实，并且包括数字设计中的其他复杂性。数字逻辑设计包括您在软件中认为理所当然的东西，即通过组合逻辑的信号需要很小但非零的时间来传播和稳定。需要仔细设计 32x32 乘法器。 1024x1024 乘法器不仅会占用芯片中的大量物理资源，而且比 32x32 乘法器慢(尽管可能比计算执行 1024x1024 乘法所需的所有部分乘积的 32x32 乘法器快)。此外，瓶颈不仅在于乘数:您还有内存通路。您必须花费大量时间从只有 32 位宽的存储器电路中收集 1024 位，并将产生的 2048 位存储回存储器电路。

几乎可以肯定，让一堆“传统”的 32 位或 64 位系统并行工作会更好:您可以在没有硬件设计复杂性的情况下获得加速。

编辑:如果有人有 ACM 访问权限(我没有)，也许看看 this paper看看它说了什么。