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

Original publish date:Jun 05, 2007

編輯 John C. H. Chen 報導

一群德國數學家藉由數百台電腦的協助,終於把一個長達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位的編碼了。「程式是很有彈性的」。

參考來源:


泛科學自製商品

【時時科科.2020】桌曆+線裝筆記本預購最後倒數!

從內子宮到外太空,科學離不開我們生活中的時時刻刻,時光走入西元 2020,讓泛科學也走入你生活的每一天!【時時科科 2020桌曆】 精選不容錯過的科學日,讓你記下屬於自己的重要日程,也記下科學史上的精彩片段。


🚀 泛科學院獨家線上新課募資 🚀 限量55折預購

【好好說話,做自己的口才教練!10堂一生受用的口語表達課】

「上台說話報告時腦袋一片空白嗎?與人對談尷尬癌就發作?如何清楚表達自己想說的話?怎麼說話才能抓住人心讓人印象深刻呢?」泛科學院與榮恩同樂會共同合作,從表達的心法到語言聲韻的技巧掌握,讓你找到自信,在家就可練出好口才!

關於作者

科景

Sciscape成立於1999年4月,為一非營利的專業科學新聞網站。

網站更新隱私權聲明
本網站使用 cookie 及其他相關技術分析以確保使用者獲得最佳體驗,通過我們的網站,您確認並同意本網站的隱私權政策更新,了解最新隱私權政策