小問題,大學問,新應用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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