暗夜間諜的密令

撰文／Dennis E. Shasha｜譯者／翁秉仁
轉載自《科學人》2002年12月第10期

過去大家認為，數論是一個詭秘的數學領域，專門研究質數的奇異性質，如今它卻成為現代密碼學的基礎。在當今電子商務交易中廣泛使用的「瑞維斯特–希米爾–艾德曼公開鑰匙密碼演算法」（RSA），就是依靠兩質數的乘積很難被因數分解的道理（大家相信這是對的，雖然尚未證明）。

兩個很大的質數相乘，正是所謂「單向函數」的例子：在電腦上，兩數相乘只需要幾微秒的時間，運算時間與這些數的二進位表示法長度大致成正比；相反的，如果給定乘積，要反求出原本的兩個質因數，就需要很長的時間，例如解一個512位元的乘積，大概要花上幾小時的時間，位數再多則呈緩慢的指數成長（相對於乘積的位數）。假設這個數有2048位元，以目前檯面上所知的方法，要對它做因數分解差不多是不可能的事情。因此，如果真能找到快速做因數分解的演算法，在產業界甚至軍事諜報上的應用都不可限量。

這帶我們來到本期的謎題。這個問題首先是由麥卡錫（John McCarthy，LISP程式語言與理論人工智慧學的發明者）提出的，1950年代被常常有妙點子的拉賓（Michael Rabin，許多重要電腦算則的發明者）給解決了。這個謎題大致如下：假設你手下有一批間諜準備進入敵境，當他們重返國境時，既要避免我方間諜在邊界被我方邊境警衛射殺，同時又要防範敵方間諜潛入，於是邊境警衛利用口令來驗明正身。雖然我們信任己方間諜，也相信警衛很忠誠，但是卻難保這些警衛晚上在酒吧消磨時不會大嘴巴亂講話。在這樣的考量下，我們應該給警衛什麼樣的口令資訊？我方間諜又應該如何說出口令，才能確保只有他們能通過，其他人卻都不行，而且就算警衛要出去喝兩杯也不會壞了大事呢？前面關於質數的討論就是提示。

_{參考答案：間謀先找到兩個隨機選取的大質數，然後將兩數的乘積交給邊境警衛。當這個間謀返國時，他就將這兩個質數交給警衛，警衛將它們乘起來，看看是否跟先前的數字相同。即使警衛將這個乘積給別人看，敵方要實際分解出這兩個質因數幾乎不可能 （假設因數分解真的很困難）。}

(本文由教育部補助「AI報報─AI科普推廣計畫」取得網路轉載授權)