分享本文至 E-mail 信箱

學術引用格式

MLA (點一下全選)

APA (點一下全選)

EndNote(.enw)

做個除法吧: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位的編碼了。「程式是很有彈性的」。

參考來源:

 

科技大觀園延伸閱讀:

也可以上科技大觀園搜尋「數學」

你的行動知識好友泛讀已全面上線

每天有成千上百則內容透過社群與通訊軟體朝你湧來,要從混雜著偽科學、假消息、純八卦的資訊中過濾出一瓢知識解渴,在這時代似乎變得越來越難?

為了滿足更多跟我們一樣熱愛知識與學習的夥伴,現在我們很害羞也很驕傲地宣布,手機閱讀平台——泛讀 PanRead iOS 版和「泛讀」Android 版都上架啦!使用後有任何心得或建議,都歡迎與我們分享喔

立即下載 優質知識不漏接

 

 

 

關於作者

科景

科景

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