小問題,大學問,新應用

在小學，同學們曾學習到正整數的一種分類，按這種分類，所有正整數可分為：質數(或稱素數)、合數和1，在做了這種分類后，同學們會進一步了解到：每個合數都可以由幾個質數相乘得到，由此引入了一個非常自然的問題：如果知道了一個數是合數，如何把這個合數分解質因數呢?一種常用的方法稱為試除法，具體地說，為了分解一個合數，我們可以試著從最小的質數2開始，用質數2，3，5，……一個一個地去試除給定的合數，看這些質數能否整除所給的合數，如果能整除，就記下除數和商，如果商仍然是合數，就重復上面的試除過程，如此炮制，一直到最后的商是質數為止，由此，就把給定的合數分解質因數了。

到此為止，一切都很簡單、很好理解，難道整數分解這個小問題真的是這樣淺顯無趣嗎?如果你這樣認為，那你可以試試下面的一個“小題目”：分解4189，你會發現，如果用上面的辦法分解30只需要幾秒鐘，那么用同樣的辦法分解4189，或許就要花費你好幾分鐘了，很不幸，4189這個數才僅有4位而已，如果要分解一個10位或20位的數，又會怎樣呢?一個有趣的故事會告訴我們答案。

1903年10月，美國數學家科爾(1861－1926)登上講臺，以一個并不醒目的標題“論大數的因數分解”開始做學術報告，只見一向沉默寡言的科爾走上講臺，一言不發地在黑板上計算起2⁶⁷(這個式子表示67個2連乘在一起)來，然后他小心地將該數減去1，得到21位的龐大數字147573952589676412927，他仍一言不發地移到黑板上的空白處，一步步地做起了乘法運算：193707721×761838257287，兩個計算結果完全相同，臺下的聽眾馬上意識到，科爾已經在這次無聲的學術報告中成功地分解了一個21位的合數2⁶⁷－1，會場上頓時響起了經久不息的掌聲，會后，當有人詢問科爾尋找這兩個質數因子用了多長時間時，科爾回答說：“三年中的全部星期天!”

由此我們可以明白。為了更好地處理大數分解的問題，人們需要尋找更好的方法，300多年前，法國數學家費馬(他以提出費馬大定理而聞名)最先找到了整數分解的新方法，下面，我們就用他的方法來分解一下上面剛剛提到的4189。

先找一個數，這個數的平方稍大于4189，我們可以取65.65的平方是4225，用這個數減去4189，得到36.36正好是6的平方，于是，我們有4189＝65²－6²而(65＋6)(65－6)＝65×65＋6×65－6×65－6²，恰好等于65²－6²(事實上，一般總有：兩數的平方差等于這兩個數的和乘以這兩個數的差)，于是，我們得到4189＝65²－6²＝(65＋6)(65－6)＝71×59，對71、59這兩個比較小的數，容易驗證它們都是質數，因此，我們就成功地把4189分解質因數了。

如果你勤于思考，你可能會問：這里找到的65的平方與4189的差正好是一個數(即6)的平方，如果這個差不是一個數的平方，該怎么辦呢?辦法是，你可以繼續試試66的平方與4189的差，67的平方與4189的差……簡單地說，費馬給出的方法是：為了分解一個數，去找另一個數，使后一個數的平方減去給定的數，差正好是一個平方數，下一步，利用上面提到的，兩數的平方差等于這兩個數的和乘以這兩個數的差，使問題得到解決，你明白費馬的方法了嗎?試試分解5251吧，你會發現，在這類例子中，費馬的方法比毫無效率的試除法確實是簡捷多了，不過，多試幾個例子你就會發現，這種方法也是有局限性的，并不是對任何一個數的分解它的工作量都如此小。

談到這兒，有同學可能會問：以前沒有計算機，大數分解是困難的，現在有了速度非常快的計算機，把事情交給計算機完成，不就行了嗎?這樣的疑問是有道理的，但問題是，在有了計算機后，分解20位數可能由困難變得簡單了，可如果分解一個40位或50位的數呢?計算機比我們手算的速度可能快多少億倍，但這在整數分解問題上所能做到的，最多不過是把可分解的整數位數提高一二十位而已，因此，要想成功地對大數進行分解，只靠計算機的高速是不大管用的。

唉呀，停一下!我們為什么要對這么高的位數的大數進行分解呢?畢竟，這種大數分解似乎是沒有任何實用價值的，放在幾十年前，對這個問題的回答可能是：做這種事，多多少少就是一些對此充滿好奇的人沒事兒找事，另一種回答也許是：正是因為這種“純正潔白”的研究沒有實際用處，所以才更具有迷人的魅力，然而，當20世紀70年代人們把大數分解與極具應用價值的密碼技術聯系在一起時，事情發生了轉折。

密碼的應用，已有悠久的歷史，最初，它應用在一些非常重要的場合，如戰爭中，交戰中，將領想把信息傳遞給自己的下屬，但又擔心在傳遞過程中，信息被截獲導致機密泄漏，如何做才能避免這種可怕的后果呢?一種有效的方式就是對信息進行加密，從而隱藏信息的意思，對原來的信息，我們稱之為明文：加密后的信息我們稱之為密文，信息的發送一方把明文轉化為密文。信息的接收方再把收到的密文轉化為明文，在此過程中，關鍵是傳送信息的一方與接收信息的一方事先要協商好某種要保密的“鑰匙”(可稱為密鑰)，用來加密和解密，在諜戰片中，經常出現的密碼本就是這種密鑰，在傳統密碼方案中，加密者和解密者必須知道同樣的密鑰，并用同一個密鑰進行加密和解密，而且只要有密鑰，加密與解密都很容易進行，但是在沒有密鑰的情況下，破譯信息是不可能的或者是非常困難的，這正是諜戰片中人們為什么要如此費心費力去得到密碼本的原因。

20世紀，特別是進入信息化時代后，這種傳統密碼方案的局限性越來越明顯，越來越無法適應人們的要求，1976年，一種非常美妙的新思想被引入了，有人想到可以設計陷阱門密碼，像任何人都很容易掉進陷阱，但是出來卻要難得多一樣，陷阱門密碼具有一種類似的進去容易出來難的“單向性”，我們可以通過一個類比來理解一下這種密碼。

我們都知道，把鎖關上是非常容易的，但只有有鑰匙的人才能把鎖打開，于是：一個人比如說甲為了得到別人的信息，可以設計一種掛鎖和鑰匙，然后自己保存好鑰匙，而把成千上萬的掛鎖分發出去(公開分發的掛鎖相當于甲的“公開密鑰”)，如果別人想發一個信息給甲，只需要把信息用甲提供的鎖鎖在箱子中寄給甲就行了，掛上鎖和鎖上的過程相當于加密，因為每個人都可以得到掛鎖，所以每個人都可以掛上鎖鎖上箱子以發送信息，因此，加密一個信息是很容易的，但因為只有甲有鑰匙(只有甲才有的鑰匙相當于甲的“私人密鑰”)，因此只有他可以打開鎖，看到箱子中的信息，其他人即使得到了掛上鎖的箱子，也知道有關鎖的知識，但這些都無助于開鎖。

可是，如何才能將這一美妙思想變成現實呢?1977年4月。三位研究者獲得了成功，于是，一種新的、在現代密碼學中最有影響的加密系統問世了，它以三位發現者(Rivest，Shamir，Adleman)名字的首字母命名。稱為RSA密碼，下面，我們用非常簡略的方式說明一下這種密碼的操作過程。

我們假設一個人比如說甲要得到別人的信息，他可以這樣做：選取兩個質數p與q，保存好這兩個數，然后算出兩者的乘積N，并把這個值公開，這個被公開的Ⅳ就是甲的公開密鑰(相當于上面類比中公開發送出去的掛鎖)，而保存好的不公開的p與q實際上就是甲的私人密鑰，如果有人比如說乙打算發信息給甲。他只需要先查到甲的公開密鑰N，然后以Ⅳ為基礎加密信息后傳給甲就行了，甲在收到乙寄來的加密信息后，可以利用自己的私人密鑰p與q解密密文，假設丙截獲了信息，他破譯密文的關鍵是要通過公開的數Ⅳ得出未公開的p與q，而這個過程是一個分解質因數的過程，我們已經知道，對于一個大數來說要分解質因數是極其困難的，因此，只要甲選定的Ⅳ的數量級達到了一定的程度，那么要想分解它。即便最先進的電子計算機也是無能為力的。

仔細體會會覺察到，這種RSA密碼系統的最優美之處在于利用了這樣一個事實：給定兩個大質數進行乘法運算得到其積是容易的，但已知乘積把它分解成原來的兩個質數卻是非常難以做到的!

為了證明這種密碼的可靠性，《科學美國人》雜志1977年8月號上發表了一篇名為《一種新的密碼，要幾百萬年才能破解》的文章，文章舉例說。為了解密某個信息，關鍵要做的是把一個129位的大數分解!按照當時通用的方法分解這個被稱為RSA-129(129指位數)的大數，人們估計至少要用幾百萬年，因為當時即便是50位數，看起來也超出了最方便的因數分解方法和電子計算機“能夠駕馭”的范圍。

然而。正是RSA密碼的提出，極大地刺激了大數分解的研究，從而在這方面出現了遠遠超出人們預料的進展，在短短的20多年里，幾種精巧絕倫的有效分解方法先后被提出，從而使人們在大數分解方面邁出了一大步。

先是在20世紀80年代初，一種與上面提到的費馬方法有關系，但卻遠為精巧、復雜的二次篩法(或稱平方篩法)出現了。它把能被分解的數的位數一下子翻了一番，以前人們一般只能分解50位左右的大數，而它一下子把原來很難分解的正整數推進到了100位的水平，隨后在1987年，有數學家提出橢圓曲線法，1980年代后期，又有數學家提出了數域篩法，數域篩法在1990年代被改進，威力大增，已成為目前世界上最快、最先進的整數分解方法，使用這種方法，現在人們已經能夠分解200位的大數了。

那么，RSA－129的命運又如何了呢?1994年，有人組織了一項以互聯網為基礎的分解RSA－129的工程，來自24個國家的600位志愿者，每人操作一至數臺個人計算機，他們合作8個多月后，最終找到了這個大數的兩個質數因子，成功地分解了這個大數，在挑戰提出17年后，RSA－129被攻克了!人們取得這一成功，除了有賴于計算機變得越來越快外、最重要的原因在于：分解中使用了當時先進的“二次篩法”。

雖然RSA－129有些短命，然而從某種意義上講，分解129位數所需要的大量工作恰恰表明了RSA保密系統的威力，這同時也表明，為了增加亓丁靠性，做到真正的保密，使用RSA密碼系統時，必須使用更高數量級的數，現在人們建議，RSA加密應當至少有240位，以保安全，在一些更重要的場合，如銀行轉帳等，可以讓N取300位的大數，這樣，恐怕1億臺電腦加起來分解它也要花費成千上萬年的時間。

我們看到，要破澤目前被廣泛使用的RSA密碼系統，就意味著需要找到更好更快的方法來進行大數分解，大數質因數的分解這個最古老的純粹數學問題與最新的學科——密碼學意外地結合了起來，由此，大數分解問題一躍而成為數學研究中的熱點問題。

一個看似簡單的小問題竟然蘊含著如此深的大學問，而一個貌似毫無實際用途的最純粹的數學課題，居然成為現代安全體系的基礎，被廣泛應用于現代社會各種各樣的場合，這一切是多么有趣，多么出人意料，又多么具有啟發意義啊!