秀尔算法(Shor算法),以数学家彼得·秀尔命名,是一个在1994年发现的,针对整数分解这题目的的量子算法(在量子计算机上面运作的算法)。比较不正式的说,它解决题目如下:给定一个整数N,找出他的质因数。
在一个量子计算机上面,要分解整数N,秀尔算法的运作需要多项式时间(时间是log N的某个多项式这么长,log N在这里的意义是输入的档案长度)。更精确的说,这个算法花费O((log N)3)的时间,展示出质因数分解问题可以使用量子计算机以多项式时间解出,因此在复杂度类BQP里面。这比起传统已知最快的因数分解算法,普通数域筛选法,其花费次指数时间-- 大约O(e1.9 (log N)1/3 (log log N)2/3),还要快了一个指数的差异。
秀尔算法非常重要,因为它代表使用量子计算机的话,我们可以用来破解已被广泛使用的公开密钥加密方法,也就是RSA加密算法。RSA算法的基础在于假设了我们不能很有效率的分解一个已知的整数。就目前所知,这假设对传统...