量子计算机分解时间,量子计算机如何分解两个质数乘积

撰文丨范桁中国科学院物理研究所

人类历史上建造了各种运行模式各异的计算机器，例如几十年前还在经常使用的计算尺，在中国普遍使用的算盘，当然也有计算机等不一而足。但是我们知道不管其运行模式如何，背后的数学必须是对的，比如算盘里二一添作五，三一三剩一这样的口诀，列为计算式也是对的。这样人们就提出一个疑问，量子计算机据称可以轻松分解两个质数的乘积，那么其背后的数学是什么呢？

知道一个大数是两个质数的乘积，求出具体两个质数，这样的大数分解问题是一个难的问题，但是把两个质数乘起来就简单很多，比如n=10,104,547是两个质数p,q的乘积，把n分解为2789和3623这两个质数，比起把它们乘起来就耗时很多。RSA公钥密码系统的安全性就是基于这样的原理，这个系统在银行和互联网是广泛使用的，其运行原理是基于所谓的费马小定理和欧拉定理，这里就不展开了。那么量子计算机是怎样分解两个质数的乘积呢？

张益唐是世界知名的科学家，他把孪生子质数问题推进了许多，孪生子质数是指两个质数只相差2，是紧挨着的，比如3和5， 11和13， 641和643等。张益唐证明相差在7000万之内的一对质数是无穷多的，很快大家就把这个距离缩减到百量级，而原始的问题是能否证明孪生子质数是无穷多的，当然我们这里的空间太小，不可能证明孪生子质数问题。还是回到大数分解问题，我们假设两个质数是孪生子质数，我们会知道他们的乘积可以写为(x+1)(x-1)=x2-1的形式，那分解它们的积就是一个简单的问题，比如可以解 x2-1=n这个式子就可以， 例如143的分解可以用143+1再开根号计算，得到x=12，这个数字加减1就可以得到11和13这两个质数。

在运行RSA密码系统中，加密和解密的计算都需要用到求n的模，即所有的数字都限制在n之内，超出了就减去n的倍数，比如14=1(mod 13), 就是指如果取13的模，14就等于1，同样15就等于2，也可以13和26就等于0。

这样的话 x2-1=n如果取n的模，就可以写为，x2-1=0 (mod n)。量子计算机就是利用这样的性质来进行计算的。具体来说，我们发现x, 然后求x+1, x-1与n的最大公约数就能求得两个质数p和q。因为(x+1)(x-1)就是pq的倍数，那么x+1和x-1就是p或者q的倍数了。当然需要指出x=1是一个解，不过是平庸的。

比如分解21，可以发现 82=64=1+3×21=1(mod 21), 那么8加减1就是7和9， 用7和9去求和21的最大公约数得到7和3, 我们知道答案21=7×3.

我们也可以试一下n=10,104,547，可以发现 59851592=n×3545192+1,用x解加减1与n求最大公约数就可以得到两个质数。

当然问题是，是否所有的n=p×q都可以用这样的方法求解，是可以的，这是由欧几里得定理保证的，就是所谓的辗转相除法。

那么量子算法具体怎么操作呢，P.Shor指出可以随便找个y, 然后求y的幂次，多求几次，我们会发现，满足 yr=1 (mod n), 而r又是偶数的概率大于50%。我们已经指出当r是偶数2m的时候，x=ym就是我们要求的方程的解。具体来讲量子计算机可以对y同时执行从0到一个比较大数字N做幂次，因为yr=1 (mod n)成立，所以幂次是按照r这个周期进行循环的，发现这个周期就成功分解了n。

以上没有任何量子的东西存在，只是说有一种算法，可以分解大数n, 而这个算法对量子计算机来说是容易的，就如同二一添作五对算盘是容易的一样，但是经典计算机是不是也可以这样做呢，当然是可以的，只是经典计算机这样做难度和直接分解n的难度是一样的，这在RSA原始的文献里就已经指出了。

以上内容在“云里悟理”讲座 “从量子计算机分解21=3×7说开去”有更详细的展示。

作者简介｜范桁

范桁，中国科学院物理研究所研究员，博士生导师，固态量子信息与计算实验室主任，课题组长，从事量子计算与量子信息理论与实验研究，近年特别致力于以多量子比特为特征，模拟诸如凝聚态多体物理、场论与统计等方面的研究，也涵盖量子算法实现、量子机器学习、量子化学模拟等内容。

每次读到RSA密码系统、Shor算法内容时，都有种感觉，简单的数字、神奇的数学、竟然还这么有用，这些内容对量子计算的研究者是基础内容，在此与大家分享。

特别声明：以上文章内容仅代表作者本人观点，不代表新浪网观点或立场。如有关于作品内容、版权或其它问题请于作品发表后的30日内与新浪网联系。