一种新的攻击RSA的量子算法

摘要

整数分解是数论中一个非常古老的难解性问题,而对于当今世界上最有名且广泛使用的RSA公钥密码体制,其安全性是基于整数分解的难解性的.迄今为止,最有希望破解RSA的方法就是Shor的量子算法.利用RSA不动点性质,基于量子Fourier变换和变量代换,提出了一种新的攻击RSA的量子算法.该算法不需要分解n,而是从RSA密文C中直接恢复其明文M.该算法与Shor算法相比,需要的量子位更少,且成功概率大于1/2.最后将新算法的资源消耗情况与Shor算法的进行了对比.