人类历史上建造了各种运行模式互异的打算机器，例如几十年前还在常常利用的打算尺，在中国普遍利用的算盘，当然也有打算机等不一而足。但是我们知道不管其运行模式如何，背后的数学必须是对的，比如算盘里二一添作五，三一三剩一这样的口诀，列为打算式也是对的。这样人们就提出一个疑问，量子打算机据称可以轻松分解两个质数的乘积，那么其背后的数学是什么呢？
知道一个大数是两个质数的乘积，求出详细两个质数，这样的大数分解问题是一个难的问题，但是把两个质数乘起来就大略很多，比如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算法内容时，都有种觉得，大略的数字、神奇的数学、竟然还这么有用，这些内容对量子打算的研究者是根本内容，在此与大家分享。
关于“墨子沙龙”
墨子沙龙是由中国科学技能大学上海研究院主理、上海市浦东新区科学技能协会及中国科大新创校友基金会协办的公益性大型科普论坛。沙龙的科普工具为对科学有浓厚兴趣、热爱科普的普通民众，力争打造具有中学生学力便可以理解当下环球最尖端科学资讯的科普讲坛。
