漂泊

做個除法吧：307位數的除法

科學新聞由SciScape提供

一群德國數學家藉由數百台電腦的協助，終於把一個長達307位的整數分解成三個質數的乘積。

目前網路上把資料加密的方法，簡單的說就是把你要傳送的資料轉換成一個質數(數A)，然後乘上另外一個很大的數(數B)來做加密的動作，而這個數B則是兩個很大的質數的乘積。目前普遍使用的RSA加密方式在傳送資料的時候會有一個公鑰(public key)，還有一組由兩個質數所構成的私鑰(privite key)。要解開由公鑰加密的訊息，就要用到由私鑰中的兩個質數來把這個公鑰解開。目前已知要破解這種加密方式的唯一作法就是硬上，把一個一個的質數拿來試。這是絕對的硬碰硬，不但考驗挑戰者的程式技術，更現實的考驗就是挑戰者的硬體設備。

這次這群由德國波昂大學的Thorsten Kleinjung領軍的數學家挑戰的是個307位長的整數，如果用二進位碼來記這個數，長度是1017位，距離我們目前所使用的1024位已經不是太遠了。為什麼現在用的是1024呢？因為上個公用標準512已經在1999年的時候被破解了...

這次的挑戰，他們利用了上百台電腦來解決這個問題。那麼解決這個問題要讓這些電腦計算多久呢？合計所有的電腦計算時間，大約是95年。這個結果簡單的說就是，這個問題可以解決，不過代價驚人。而這次成功解決這個問題的關鍵之一是技術方面的突破，解決了其中"matrix step"的限制。

瑞士Swiss Federal Institute of Technology的Arjen Lenstra則表示目前市面上的電視遊樂器Play Station 3，由於是專門設計用來處理數字運算，所以可能在處理分解質數上會有很好的表現。因此Kleinjung就表示，他考慮集合上千台或是上萬台PS3來實際測試PS3的能力。

對於密碼有遭破解的風險，RSA的發明人之一，MIT的Ronald Rivest就認為數學家對分解質數的進展當然會是編碼技術的威脅。不過他似乎並不在意，只簡單的表示：他們早就建議用2048位的編碼了。「程式是很有彈性的」。