使用特制的CPU查找大数的主要因素

我的理解是,目前许多公钥加密算法依赖于大质数来构成密钥,并且难以将两个素数的乘积分解,使加密难以破解。我的理解是,将如此大的数字分解的原因之一是,使用数字的绝对大小意味着没有CPU可以有效地操作数字,因为我们的32位和64位CPU是微不足道的对于1024,2048甚至4096位数。必须使用专门的Big Integer数学库来处理这些数字,并且这些库本质上很慢,因为CPU一次只能保存(和处理)小块(如32或64位)。 所以... 为什么你不能用2048位寄存器和巨大的算术电路构建一个高度专业化的定制芯片,就像我们从8到16到32到64位CPU的缩放一样,只需构建一个更大的?该芯片不需要传统CPU上的大部分电路,毕竟它不需要处理虚拟内存,多线程或I / O等内容。它甚至不需要是支持存储指令的通用处理器。只是在最大数量上执行必要的算术计算的最低限度。 我不太了解IC设计,但我确实记得了解逻辑门如何工作,如何构建半加器,全加器,然后将一堆加法器链接在一起进行多位算术。只是扩大规模。很多。 现在,我相当确定有一个非常好的理由(或17)以上不会起作用(因为否则会比我更聪明的人中的一个人已经做过了)但我有兴趣知道为什么它不会起作用。 (注意:这个问题可能需要一些重新工作,因为我甚至不确定这个问题是否有意义)     
已邀请:
@cube说的是什么,以及巨大的算术逻辑单元需要更多的时间让逻辑信号稳定,并在数字设计中包含其他复杂功能。数字逻辑设计包括您在软件中认为理所当然的东西,即通过组合逻辑的信号需要很小但非零的时间来传播和稳定。需要仔细设计32x32乘法器。 1024x1024乘法器不仅会占用芯片中的大量物理资源,而且还会比32x32乘法器慢(尽管可能比计算执行1024x1024乘法所需的所有部分乘积的32x32乘法器更快)。此外,它不仅是瓶颈的乘数:你有记忆途径。您必须花费大量时间从仅32位宽的存储器电路收集1024位,并将产生的2048位存储回存储器电路。 几乎可以肯定,最好让一堆“常规”32位或64位系统并行工作:您可以获得没有硬件设计复杂性的加速。 编辑:如果有人有ACM访问权限(我不这样做),或许可以看一下这篇论文,看看它的内容。     
因为这个加速仅在O(n)中,但是将数字分解的复杂性类似于O(2 ^ n)(相对于比特数)。因此,如果您使用这个超级处理器并将数字分解为1000倍,我只需要将数字增大10位,我们就会重新开始。     
如上所述,主要问题是您需要通过多少种可能来计算一个数字。话虽这么说,确实存在专门的计算机来做这种事情。 这种加密技术的真正进步是数字因子分解算法的改进。目前,最快的已知通用算法是一般数字域筛。 从历史上看,我们似乎能够将每十年的数字提高两倍。其中一部分是更快的硬件,其中一部分只是更好地理解数学以及如何执行因子分解。     
我无法评论与您描述的方法完全相同的方法的可行性,但人们使用FPGA经常做类似的事情: 破解DES密钥 破解GSM对话 开源图形卡     
沙米尔& Tromer提出了一种类似的方法,使用一种网格计算:   本文讨论了自定义硬件的新设计   实施筛分步骤,其中   将[相对于TWINKLE的筛分成本]降低至约1000万美元。新设备,   叫TWIRL,可以看作是一个延伸   TWINKLE设备。但是,不像TWINKLE那样   没有光电元件,并且可以   因此可以使用标准VLSI技术制造   在硅片上。根本的想法是使用   输入的单个副本以解决许多子问题   在平行下。由于输入存储主导成本,如果   并行化开销保持低,然后得到   加速是基本上免费获得的。的确如此   主要挑战在于有效实现这种并行性,同时允许输入的紧凑存储。   解决这个问题涉及无数的考虑因素   从数论到VLSI技术。     
你为什么不尝试构建超级量子计算机并在其上运行Shor的算法?   “...如果要构建具有足够数量的量子比特的量子计算机,Shor的算法可用于破坏公钥加密方案,例如广泛使用的RSA方案.RSA基于假设分解大数是计算上不可行。到目前为止,这个假设对于经典(非量子)计算机是有效的;没有经典算法可以考虑多项式时间。然而,Shor的算法表明因子分解在量子计算机上是有效的,所以足够大的量子计算机可以打破RSA ......“ - 维基百科     

要回复问题请先登录注册