知道一個大數是兩個質數的乘積，求出具體兩個質數，這樣的大數分解問題是一個難的問題，但是把兩個質數乘起來就簡單很多，比如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原始的文獻裡就已經指出了。
範桁，中國科學院物理研究所研究員，博士生導師，固態量子信息與計算實驗室主任，課題組長，從事量子計算與量子信息理論與實驗研究，近年特别致力於以多量子比特為特徵，模擬諸如凝聚態多體物理、場論與統計等方面的研究，也涵蓋量子算法實現、量子機器學習、量子化學模擬等內容。
每次讀到RSA密碼系統、Shor算法內容時，都有種感覺，簡單的數字、神奇的數學、竟然還這麼有用，這些內容對量子計算的研究者是基礎內容，在此與大家分享。
推薦閱讀