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

摘要

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