量子計算機如何分解兩個質數乘積

人類歷史上建造了各種運行模式各異的計算機器，例如幾十年前還在經常使用的計算尺，在中國普遍使用的算盤，當然也有計算機等不一而足。但是我們知道不管其運行模式如何，背後的數學必須是對的，比如算盤裏二一添作五，三一三剩一這樣的口訣，列為計算式也是對的。這樣人們就提出一個疑問，量子計算機據稱可以輕鬆分解兩個質數的乘積，那麼其背後的數學是什麼呢？

知道一個大數是兩個質數的乘積，求出具體兩個質數，這樣的大數分解問題是一個難的問題，但是把兩個質數乘起來就簡單很多，比如n=10,104,547是兩個質數p,q的乘積，把n分解為2789和3623這兩個質數，比起把它們乘起來就耗時很多。RSA公鑰密碼系統的安全性就是基於這樣的原理，這個系統在銀行和互聯網是廣泛使用的，其運行原理是基於所謂的費馬小定理和歐拉定理，這裏就不展開了。那麼量子計算機是怎樣分解兩個質數的乘積呢？

張益唐是世界知名的科學家，他把孿生子質數問題推進了許多，孿生子質數是指兩個質數只相差2，是緊挨着的，比如3和5， 11和13， 641和643等。張益唐證明相差在7000萬之內的一對質數是無窮多的，很快大家就把這個距離縮減到百量級，而原始的問題是能否證明孿生子質數是無窮多的，當然我們這裏的空間太小，不可能證明孿生子質數問題。還是回到大數分解問題，我們假設兩個質數是孿生子質數，我們會知道他們的乘積可以寫為（x 1）(x-1)=x2-1 的形式，那分解它們的積就是一個簡單的問題，比如可以解 x2-1=n 這個式子就可以， 例如143的分解可以用143 1再開根號計算，得到x=12，這個數字加減1就可以得到11和13這兩個質數。

在運行RSA密碼系統中，加密和解密的計算都需要用到求n的模，即所有的數字都限制在n之內，超出了就減去n的倍數，比如14=1（mod 13）, 就是指如果取13的模，14就等於1，同樣15就等於2，也可以13和26就等於0。

這樣的話 x2-1=n 如果取n的模，就可以寫為，x2-1=0 （mod n）。量子計算機就是利用這樣的性質來進行計算的。具體來説，我們發現x, 然後求x 1, x-1與n的最大公約數就能求得兩個質數p和q。因為(x 1)(x-1)就是pq的倍數，那麼x 1和x-1就是p或者q的倍數了。當然需要指出x=1是一個解，不過是平庸的。

比如分解21，可以發現 82=64=1 3×21=1（mod 21）, 那麼8加減1就是7和9， 用7和9去求和21的最大公約數得到7和3, 我們知道答案21=7×3.

我們也可以試一下n=10,104,547，可以發現 59851592=n×3545192 1 ,用x解加減1與n求最大公約數就可以得到兩個質數。

當然問題是，是否所有的n=p×q都可以用這樣的方法求解，是可以的，這是由歐幾里得定理保證的，就是所謂的輾轉相除法。

那麼量子算法具體怎麼操作呢，P.Shor指出可以隨便找個y, 然後求y的冪次，多求幾次，我們會發現，滿足 yr=1 (mod n) , 而r又是偶數的概率大於50%。我們已經指出當r是偶數2m的時候，x=ym 就是我們要求的方程的解。具體來講量子計算機可以對y同時執行從0到一個比較大數字N做冪次，因為yr=1 (mod n)成立，所以冪次是按照r這個週期進行循環的，發現這個週期就成功分解了n。

以上沒有任何量子的東西存在，只是説有一種算法，可以分解大數n, 而這個算法對量子計算機來説是容易的，就如同二一添作五對算盤是容易的一樣，但是經典計算機是不是也可以這樣做呢，當然是可以的，只是經典計算機這樣做難度和直接分解n的難度是一樣的，這在RSA原始的文獻裏就已經指出了。

以上內容在“雲裏悟理”講座 “從量子計算機分解21=3×7説開去”有更詳細的展示。