π导航  


【首页】

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


【2021-03-23】 【教育】


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

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

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

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

 这样的话 x^2-1=n 如果取n的模,就可以写为,x^2-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,可以发现 8^2=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的幂次,多求几次,我们会发现,满足 y^r=1 (mod n) , 而r又是偶数的概率大于50%。我们已经指出当r是偶数2m的时候,x=y^m 就是我们要求的方程的解。具体来讲量子计算机可以对y同时执行从0到一个比较大数字N做幂次,因为y^r=1 (mod n)成立,所以幂次是按照r这个周期进行循环的,发现这个周期就成功分解了n。

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

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



                        
   
        

copyright©2018-2021 gotopie.com