博志Bojhih 國中資優數學理化

為什麼要學質數？

RSA演算法終於讓質數有了大應用，但何以質數要納入基礎數學的學習大綱？

撰文／張海潮

　　我在讀小學的時候，有一陣子對質數非常著迷。我的生日17號是質數，圍棋棋盤19路是質數，人過世了做7是質數，黑色13號星期五是質數，甚至當年有一線到三張犁的公車43路，也是質數。

　　著迷歸著迷，不過是發現了身邊有些數恰好是質數，仔細想來，常見的數中，非質數反而更多。

　　進了數學系之後，頗有一些質數的理論要學，但是似乎與應用沾不上邊。以與數學最靠近的物理來說，大致沒有什麼物理概念是跟質數扯上關係的。假想某一個實驗的結果是「粒子A的質量是粒子B質量的23倍」，23是質數這件事，應該不會牽拖到任何物理意涵吧？

　　的確，有很長的一段時間，質數理論只局限在純數學的範疇。一直到1978年，美國麻省理工學院的瑞維斯特、希米爾、艾德曼聯手出擊，將質數帶進密碼系統，發明了「RSA密碼演算法」（RSA cipher algorithm），並廣泛在商業上使用，人們才如夢初醒：原來，純數學的研究也可以開啟巨大的商機。

RSA密碼演算法可簡短描述如下：

　　銀行為了讓客戶可以利用電子通訊來進行客戶與銀行之間私密的商業行為，對外公佈兩個數N、e，其中N＝pq是兩個質數p、q的乘積，e是一個與（p－1）（q－1）互質的數，亦即e和（p－1）（q－1）除了1以外，無任何公因數。N與e稱為公鑰，每個人都可以看到，但是卻無法知道N背後的p和q，當然也不知道（p－1）（q－1）的值。

　　客戶先把委託銀行處理的文件（例如要求匯出一筆款項）數位化之後，得到一個小於p、q的數目a，a稱為明文。然後將ae除以N之後的餘數r傳給銀行，r稱為密文。從a得到r的過程稱為加密，截密者可以截到r，但是無法知道a。

　　銀行本身則保留一個密鑰d，滿足ed除以（p－1）（q－1）的餘數是1。在接到客戶送來的密文r之後，銀行計算rd，然後再除以N，餘數就是客戶原始的明文a。

　　整個保密的關鍵在於截密者不知道p和q，如果知道，就可以據以算出（p－1）（q－1），並且透過e來算d。因此p和q必須是一個「至少數百位的大質數」，讓截密者永遠無法將N分解為p、q的乘積。

http://sa.ylib.com/MagCont.aspx?Unit=columns&id=1519

．張海潮教授為台大數學系退休教授，曾任數學系系主任，台灣數學界重量級人物，現今為國民中小學「數學學習領域」教科圖書審定委員會主任委員。

．RSA加密演算法是一種非對稱加密演算法。在公開金鑰加密和電子商業中RSA被廣泛使用。RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

※延伸閱讀》

．大陸旅美張益唐 破解百年數學難題

接下來是工商廣播時間~

謝謝收看~~