因式分解与密码

李迎新

在日常生活中，我们取款、上网等都需要密码，有一种用“因式分解法”产生的密码，方便记忆.原理是：如将多项式x4-y4进行因式分解，结果是（x+y）（x-y）（x2+y2），若取x=9、y=9，则各个因式的值是：x-y=0、x+y=18、x2+y2=162，于是就可以把“018162”作为一个六位数的密码.大数的因式分解是网络安全协议的核心，比如最常见的RSA加密算法.

数学家彼得·肖尔于1994年构造了大数的质因数分解算法，证明在多数情况下利用量子计算机能够对大数进行分解，从而从根本上动摇了当代密钥的安全基础.如果量子计算使得RSA加密不再安全，那用什么来取代它呢？答案是量子密码.

2012年8月20日，据物理学家组织网报道，美国加州大学圣巴巴拉分校的研究人员设计和制造了一台量子处理器，可成功将合数15分解成3和5的乘积.虽然这只是一个最基本的质因数分解运算，但这项突破性成果是研制可进行更复杂因式分解运算的量子计算机道路上的一个里程碑，对于数字加密和网络安全具有重要意义.该研究结果发表于《自然·物理》杂志网络版.论文的第一作者埃里克·卢塞罗说：“15虽是一个小数字，但重要的是，我们已经证明，我们可以在一台固态量子处理器上运行彼得·肖尔提出的质因数分解算法.这是此前从未进行过的.”

卢塞罗是出于实际应用的目的开展这项研究的.他解释说，目前最常见的RSA加密算法公开的最大密钥包含600多个十进制数字，如果利用经典计算机和最知名的经典算法，对这个密钥进行因式分解需要花费的时间可能比宇宙的年龄还要长.比RSA加密更安全的量子密码，它不仅更难被破译，而且如果有人试图盗取信息，它就会改变系统，使发送方和接收方都能够察觉.

（作者單位：江苏省淮安外国语学校）