Shor大数质因子分解算法

来自计算思维百科
跳转至: 导航搜索

Shor于1994年提出的大数质因子分解量子算法吸引了许多研究者的目光。这是因为大数质因子分解的难度确保了RSA公钥密码体系的安全,该问题至今仍属于NP难题,在经典计算机上需要指数时间才能完成。但是Shor算法表明,在量子计算机中,这一问题可以在多项式时间内得到解决。这就意味着目前广泛应用于政府、军事以及金融机构等重要方面的RSA公钥密码体系的安全性可能面临着致命的威胁。

Shor算法的基本思想是:首先利用量子并行特点通过计算获得所有的函数值,并利用测量函数得到相关的函数自变量叠加态,然后对其进行快速傅里叶变换。其实质是利用数论相关知识将大数质因子分解问题转化为利用量子快速傅里叶变换求函数的周期问题。

Shor算法证明了大数质因子分解问题可以在多项式时间内解决,量子算法在解决一些经典算法无法解决的问题时确实显示出优越性。Shor算法是目前为止已经提出的最好的量子算法,该算法不但具有传统算法无法比拟的优势,而且其巧妙的理论构思以及表现出的实际应用价值,都是十分宝贵的。Shor算法及其模拟实现,对量子通信和量子密码学的发展都具有极其重要的参考价值。