ice 秀尔算法(Shor）以应用数学家彼得·秀尔(Peter Williston Shor )命名，是一个在1994年发现的，针对整数分解问题的量子算法 (在量子计算机上面运作的算法 )。
在一个量子计算机上面，要分解整数N,秀尔算法的运作需要多项式时间（时间是log N的某个多项式这么长,log N在这里的意义是输入的档案长度）。更精确的说，这个算法花费O((log N)3)的时间，展示出质因数分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类BQP里面。这比起传统已知最快的因数分解算法，普通数域筛选法，其花费次指数时间 -- 大约O(e1.9 (log N)1/3 (log log N)2/3)，还要快了一个指数的差异。
秀尔加密算法非常重要，因为它代表使用量子计算机的话，可以用来破解已被广泛使用的公开密钥加密方法，即RSA加密算法。RSA算法的基础在于假设了我们不能很有效率的分解一个已知的整数。就目前所知，这假设对传统的（也就是非量子）电脑为真；没有已知传统的算法可以在多项式时间内解决这个问题。然而，Shor算法展示了因子分解这问题在量子计算机上可以很有效率的解决，所以一个足够大的量子计算机可以破解RSA。这对于鼓吹我们去建立量子计算机和去研究新的量子计算机算法，是一个非常大的动力。
我们要试着解决的问题是：给定一个合成数N,找到整数p在1和N之间且不包含1和N,并且N整除于p。
秀尔加密算法包含两个部分：
一个以传统的电脑运作的简化算法，将因数分解简化成搜寻目的问题。
一个量子算法，解决搜寻目的问题。
传统部分：
1、选择任意数字a < N
2、计算gcd（a, N）。这里可以使用辗转相除法来计算。
3、若gcd(a, N) ≠ 1，则我们有了一个N非平凡的因数，因此这部分结束了。
4、否则，利用下面的周期寻找副函式（Period-finding subroutine，下面会列出）来找出下面这个函数的周期r：f (x) = a^x mod N,换句话说，找出a在Zn里面的阶r，或者最小的正整数r令f(x+r)=f(x)。
5、若r是奇数，回到第一步。
6、若a r /2 ≡ -1 (mod N),回到第一步。
7、gcd(ar/2+1, N)与gcd(ar/2-1, N)分别是N非平凡的因数。分解完成。
量子部分：
这个算法使用的量子线路是为了在给定一个固定常数N以及一个任意常数a之下，找出f(x) = ax mod N所设定的。给定N,找出Q = 2q且合乎N^2 大于等于 Q 小于2N^2（这同时表示 Q/r > N）。输入和输出量子位元暂存器需要储存从0到Q-1所有值的叠加态，因此分别需要q个量子位元。这里使用看起来比所需的数量还要更多一倍的量子位元，保证了即使周期r的大小逼近N/2，也至少有N个不同的x会产生相同的f(x)。
1、将暂存器初始化成
x从0到Q − 1。所以这一个初始态是Q个状态的叠加。
2、建立量子函式版本的f(x)，并且应用于上面的叠加态，得到
这里仍旧是Q个状态的叠加。
3、对输入暂存器进行量子傅立叶变换。这个变换（操作于二的幂次--Q = 2q个叠加态上面） 使用一个Qth 单位根例如
由此得到最终状态：
这是一个远多过Q个状态的叠加态，但是远低过Q2个。虽然在和中有Q2项，但只要x0和x的值相同，态|y|f(Xo)就可被提出来。令
这一求和的每一项代表一个获得相同结果的不同路径，而量子干涉发生。在单位向量W^ryb几乎与复平面指向同一方向（要求W^yb指向正实数轴）时，干涉将是相长的。
4、进行测量。我们由输入寄存器取得结果y，由输出寄存器取得 f(X0)。而既然f是周期，对某对y和f(Xo)进行测量的概率则由
给出。分析显示这个概率越高，单位向量W^xy就越接近正实数轴，或者yr/Q就越接近一个整数。除非r是2的乘方，否则它不会是Q的因子。
5、对y/Q进行连分数展开来计算其近似值，并生成满足下列两个条件的c/r′：
- A: r′<N
- B: |y/Q - c/r′| < 1/2Q
借着满足这一些条件，r′有很高的概率会是我们要找的周期r。
6、检查f(x) = f(x + r′)双向等于 a^r mod{N}。如果成功了，我们就完成了。
7、否则，以接近y左右的数值作为r的候选，或者说多取几个r′.如果任何候选成功了，我们就完成了。否则，还是需要回到第一步骤，重新全部操作一次。
秀尔算法包含两个部分。算法的第一部分是将因数分解问题转成寻找一个函式的周期，而且这部分可以用传统方式实做。第二部分则是使用量子傅立叶变换来搜寻这个函式的周期，而且这一部分是量子加速这整个算法的理由。
小于N且互质于N的整数组成一个有限大，且对乘法同余N的群。在步骤3之后，我们有一个属于这个群的整数a。既然这个群是有限的，a必有一个有限大的阶r,也就是最小的正整数令a^r 等于 1 mod N.,因此可知，N是a r − 1的因数。先假设我们有能力获得r，而且r是偶数。则
证明：为了简化，我们分别用u和v表示（a r / 2 − 1）和（a r / 2 + 1）。N | uv，故kN = uv（k是某个整数）。假设gcd(v, N) = 1：则必定存在某个整数m和n令mv + nN = 1 (这是最大公因数的一个性质)。两边同乘以u，我们得到mkN + nuN = u, so N | u。gcd(v, N) ≠ 1，故产生矛盾。用类似的方法，可以得知若（a r / 2 + 1）不能整除于N, gcd(u, N) ≠ 1。故得证u和v不同时与N互质。这给予我们一个N的因数分解。若N是两个质数的乘积，则这是唯一可能的分解。
