跳到主要內容
:::
:::
:::

漫話科技_生活中的質數

MOST
MOST
MOST
MOST

說明文章:

 

國小的時候,我們學會了質因數分解。只能被1和自己整除的自然數,叫做質數,否則就叫做合成數。當數字很小如137或251,可以很快知道它是不是質數。但如果是很大的數字,要對它進行質因數分解則變得相當困難。事實上,以第23個梅森數為例,它等於8,388,607,那麼,它究竟是質數還是合成數呢?如果要測試一個982萬位數的梅森數是否為質數,使用桌上型電腦也要花幾個月的時間。

 

去年(2018)年底「網際網路梅森質數大搜索」(GIMPS) 宣布找到目前所知第51個梅森質數,也是最大的質數「282589933 - 1」,這個龐大的質數竟然高達兩千五百萬位數!這麼大的質數好像和我們沒甚麼關聯,但其實它的應用就在日常生活中。1978年,羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)三人共同將質數帶進密碼學的範疇,發明了「RSA加密演算法」(RSA cryptosystem)。

 

RSA加密演算法是基於兩質數湊出資料加密及解密的兩把鑰匙。它保密關鍵即是利用大質數難以被分解的特性作為編碼規則,儘管全世界共用相同的編碼規則,但文件經過加密後,加密者以外的人很難將其解密成原始訊息。舉例來說,631和883是質數,兩數相乘後得557,173。鎖碼金鑰是557,173,而解碼質數是 631和883。為了確保資料安全性,實際應用的金鑰是利用非常大的數字。RSA公司曾經提供 20 萬美元獎金,只要能找到一個617位數的數字的兩個質因數,即可領獎,卻由於沒有人能破解,獎金也撤銷了。或許最開始的人沒有想到質數這種純數理的研究,能被廣泛用於現今金融及商業系統資料的傳遞。

 

梅森質數:「2n - 1」形式之質數。

 

參考資料:

CASE報科學【發現最大質數】

https://case.ntu.edu.tw/blog/?p=33521

 

找到超級大質數能幹嘛?

https://sites.google.com/a/g2.nctu.edu.tw/unimath/manuscript/cryptographic

 

《桑老師的瘋狂數學課》台北市:臉譜出版。
更新日期 : 2019/11/15