
对于传统计算机来说,将非常大的数字分解为它们的主要“构建块”是非常困难的,并且这种困难是许多密码算法的安全性的基础。虽然很容易将数字20分解为素数2 x 2 x 5的乘积,但例如,在使用经典分解算法时,分解大数字会成倍地变得更加困难。
在Physical Review A发表的一篇新论文中,物理学家Jose Luis Rosales和Vicente Martin开发出了一种方法,可以更容易地分解已知具有两个主要因素的非常大的数字。新方法确定任何素数是给定数字的两个主要因素之一的概率。在确定了这些可能性之后,最可能的首要因素候选人可以首先进行测试,从而可以比以前更快地发现主要因素。
罗萨莱斯告诉Phys.org: “该理论不仅显示了素数的位置,还显示了质数是给定数的一个因素的概率。“当然,这对密码学有影响,因为[密码系统] RSA忽略了这种规律性。”
新方法的一个有趣之处在于它不使用任何类型的计算机,无论是经典还是量子。相反,它涉及到一个物理量子系统-一个“ 量子模拟器 ”,也就是说,当与数字编码以因素,表现出概率分布的能量值的,它等效于该编码数的素因子候选的概率分布。
“我们的目标是利用量子模拟器开发出一个新的分解问题的量子理论,”Rosales说。“我们的方法发现了一个在数论中没有经典类比的性质,每一对解决问题的素数都会重新排列,形成一个规则模式:量子模拟器的频谱。”
量子模拟器背后的一般概念是所谓的“分解综合体”,研究人员之前介绍过。它基于这样的想法:素数从最小到最大排序(例如,2是第一个素数,3是第二个素数,101是第26 个素数)。也可以取任意数的平方根,然后将结果与最接近的素数进行比较。例如,27的平方根大于5,这是第三个素数。通过分解集合的定义,这意味着27属于3的分解集合。
然后物理学家表明他们可以将分解综合函数转化为量子物理的函数(反演谐振子函数)。经过更多的步骤后,他们最终表明,量子系统的预测能谱对应于一个数的分解集合中素数的分布。从这些信息中,研究人员可以确定素数是该数字的一个因素。为了检验他们方法的有效性,物理学家测试了一些数字,并将他们的结果与使用素数表格获得的实际分布进行了比较,发现了非常相似的分布。
物理学家从理论上证明,所提出的量子模拟器可以将数量比那些用量子计算机计算的数量要大许多数量级。在他们的论文中,他们报告使用他们的方法来确定24位数的主要因素的概率分布的结果。此外,该方法的资源远少于经典分解算法所需的资源。
“在量子理论中,算法的复杂性只是多项式,其数字的位数要因式分解,”Rosales说。“事实上,我们的第一个结果似乎证实,模拟器只需要(log√N)3个量子态来重现其能量谱,这是一个非常令人鼓舞的结果。”
最后一点值得注意的是,新方法与黎曼假设具有很强的联系,如果这一假设是正确的,那么就表明质数是以可预测的方式分布的 – 就像黎曼分布的零点分布一样, ζ功能。证明(或驳斥)黎曼假设是数学中最大的未解决的问题之一,也是克莱数学研究所的千年奖问题之一。
“如果希尔伯特 – 波利亚猜想适用,素数应该表现为量子数,”罗萨莱斯说,指的是证明黎曼假说的长期方法。
展望未来,研究人员正在通过在Penning陷阱中使用两个纠缠粒子来研究量子模拟器的实验实现。
“模拟器的完全量子处理需要量子光学分析光子与Penning阱中两个(或更多)纠缠离子的相互作用,”Rosales说。“这部分程序尚在开发中,其目的是通过实验建立一个量子因数分解模拟器,如果成功实现,那么比使用Shor算法的量子处理可用的数量大很多数量级的数量将被分解,并且作为 – 产品,希尔伯特 – 波利亚猜想将通过实验测试。“