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

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

知道一个大数是两个质数的乘积，求出具体两个质数，这样的大数分解问题是一个难的问题，但是把两个质数乘起来就简单很多，比如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原始的文献里就已经指出了。

作者简介｜范桁

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

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

关于“墨子沙龙”

墨子沙龙是由中国科学技术大学上海研究院主办、上海市浦东新区科学技术协会及中国科大新创校友基金会协办的公益性大型科普论坛。沙龙的科普对象为对科学有浓厚兴趣、热爱科普的普通民众，力图打造具有中学生学力便可以了解当下全球最尖端科学资讯的科普讲坛。