​撰文丨範桁 （中國科學院物理研究所）

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

知道一個大數是兩個質數的乘積，求出具體兩個質數，這樣的大數分解問題是一個難的問題，但是把兩個質數乘起來就簡單很多，比如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算法内容時，都有種感覺，簡單的數字、神奇的數學、竟然還這麼有用，這些内容對量子計算的研究者是基礎内容，在此與大家分享。

關于“墨子沙龍”

墨子沙龍是由中國科學技術大學上海研究院主辦、上海市浦東新區科學技術協會及中國科大新創校友基金會協辦的公益性大型科普論壇。沙龍的科普對象為對科學有濃厚興趣、熱愛科普的普通民衆，力圖打造具有中學生學力便可以了解當下全球最尖端科學資訊的科普講壇。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!