「數學思維繫列」你可能不知道,小學學的素數既有趣又有用還很難

大家在小學就學過素數了，素數也叫質數，就是除了1和自身之外沒有其他約數(也叫因數) 的自然數，比如2、3、5、7、11等都是素數，而4、6、8、9就不是(這種數叫做合數)。回顧了素數的概念後，下面我們來聊聊與素數有關的有趣話題。

2是最小的素數，也是唯一的偶素數，2在所有素數中的地位和價值是非常獨特的，我們已經在《你可能不知道的數字2》中進行了比較詳細的介紹。

根據素數的定義和性質，任何一個自然數都可以分解為若干個素數的乘積。素數的個數是無限多的，歐幾裡得在《幾何原本》中給出了一個非常經典的反證法證明，感興趣的讀者可以看參考文獻1了解這個證明過程。素數有非常多有意思的性質和命題，有些命題比較簡單，很容易證明，比如剛剛提到的素數個數是無限多的。有很多卻非常困難，幾百年以來，都沒有被世界的數學家解決，這其中最出名的要數哥德巴赫猜想了。哥德巴赫猜想是說，任何大於等於4的偶數，都可以表示為兩個素數之和。目前關於這一命題最好的結果是我國知名數學家陳景潤的結論，陳景潤證明了：一個充分大的偶數必定可以寫成一個素數加上一個最多由2個質因子所組成的合數。

上面是素數基礎知識的介紹，看起來素數是數學家研究的話題，其實不然，素數與我們的生活密切相關，素數的如下3個性質是非常重要的。

非常大的整數是難以分解為素因子的乘積的，需要非常大的計算量；

素數沒有1和本身之外的因子，素數和與它互質的數的最小公倍數是它們的乘積；

素數在自然數中的分布是沒有什麼規律的；

下面我們來談談在自然界和人類生活中素數的價值，這些價值的發揮基本都與上面素數的3個特性有關。

在汽車變速箱齒輪的設計上，相鄰的兩個大小齒輪齒數設計成素數，以增加兩個齒輪內兩個相同的齒相遇嚙合次數的最小公倍數(即是這兩個齒輪齒數的乘積，兩個素數的最小公倍數就是它們的乘積)，這可以防止有的齒經常和另一個齒輪的某一齒單一接觸(特別是當這個齒設計有一些小的缺陷時，任何機械工程都是有一些小誤差的)，可增強耐用度、減少故障。

圖1：齒輪之間的咬合，如果每個齒輪是

上述齒輪齒數的設計其實是用到了素數與它互質的數的最小公倍數是它們的乘積這一性質，這一性質在生物學上也有比較有意思的現象。大家熟知的知了，學名叫做蟬，在自然界進化出了非常特別的繁殖周期，目前發現的有13年蟬、17年蟬等(讀者可以看參考文獻了解更多細節)，也就是它們的幼蟲需要在地底下分別生活13年、17年才能破土而出，蟬出土後的生命一般只有2個月左右，為了綻放兩個月的生命，它們需要在毫無光亮的地底下生活13年、17年，生命是多麼的神奇和偉大啊！

13年蟬、17年蟬之所以進化出這種奇特的繁殖周期，是為了逃避天敵的侵害並安全延續種群，因而演化出一個漫長而隱秘的素數生命周期(13、17都是素數)。當蟬的繁殖周期是13、17年時，蟬與它的天敵繁殖周期碰到一起就需要經過它們繁殖周期的乘積這麼多年，而如果他們的繁殖周期碰到一起的話，天敵的幼蟲就會以蟬的幼蟲為食，對蟬的種群延續是很不利的。蟬進化出這麼奇怪的繁殖周期就是為了避免天敵的傷害，這裡我們進一步看到了生物進化的魅力。

除了蟬以外，在害蟲的生物生長周期與殺蟲劑使用之間的關係上，殺蟲劑的質數次使用的有效性也得到了科學的證明：實驗表明，質數次數地使用殺蟲劑是最合理的，並且需要在害蟲繁殖的高潮期使用，這樣害蟲很難產生抗藥性。這樣使用主要是為了將相鄰批次的繁殖期的害蟲都被殺蟲劑殺掉，避免了不同次代的害蟲之間的交配繁殖。

在軍事領域，以質數形式發出的無規律變化的飛彈和魚雷可以使敵人不易攔截，這是利用了素數分布的無規律性。

素數在我們日常生活中也非常有用，大家每個人都有很多帳號和密碼，素數與他們都有關係。素數與我們生活最相關的應用要數在密碼學上的應用了。現在比較安全的密碼很多都是基於素數理論構建的，它主要利用了將一個非常大的整數分解為素因子是一件非常困難的事情這一特性。基於素數構建的複雜密碼體系，在有限的時間和現有的計算資源下基本是無法破解的。

我們知道，任何一個自然數都可以分解為素數的乘積，如果不計因數的次序，分解形式是唯一的。這叫做算術基本定理。但是將一個大整數分解卻沒有一個簡單易用的好方法，只能用較小的素數一個一個去試除，耗時極大。如果用計算機來分解一個100位的數字，所花的時間要以萬年計。可是將兩個100位的數字相乘，對計算機卻十分容易。美國數學家就利用了這一點發明了編制容易而破譯難的密碼體系，這種編碼方式以三位發明者姓氏的首字母命名為RSA碼。下面我們就來簡單說明這種密碼是怎麼巧妙利用素數來構建的。

RSA密碼的加密解密算法

下面講解RSA密碼的算法原理，我們可以通過如下8步來進行加密和解密，具體如下：

（1）選擇一對不同的、足夠大的素數p、q (p, q嚴加保密，不讓任何人知道，p、q越大，也越難破解)；

（2）計算n=p*q；

（3）計算f(n)=(p-1)*(q-1) ；

（4）找一個與f(n)互質的數e，滿足 1<e<f(n)；

（5）計算d，使得d*e ≡ 1 mod f(n)；

這裡 ≡ 是數論中表示同餘的符號。公式中 ≡ 符號的左邊必須和符號右邊同餘，也就是兩邊模運算結果相同。顯而易見，不管f(n)取什麼值，符號右邊1 mod f(n)的結果都等於1；符號的左邊d與e的乘積取模運算後的結果也必須等於1。這就需要計算出d的值，讓這個同餘等式能夠成立，一般可以通過逐個嘗試的方法找到可行的d；

（6）公鑰KU=(e, n)(公鑰就是可以公開的，大家都可以知道)，私鑰KR=(d,n)(私鑰需要自己保密，用於破解密碼用)；

（7）對於0至n-1之間的任意一個整數M，可以這樣加密：C≡M^e(mod n)(這裡M^e是指M的e次方，下面類似)，C就是需要傳輸的信息，將C給到你想傳遞信息的人；

（8）接收人收到信息C後，通過計算D=C^d(mod n)，就獲得了原來的信息M，即D=M；

如果傳輸的信息很多，可以利用0、1、2、......、n-1 對信息進行編碼(比如需要傳輸的是英文單詞，可以對每一個字母編碼，可以根據字母順序編碼，a->1、b->2、c->3、以此類推)。下面我們講個例子讓大家更好地理解上面的原理的正確性。對這個感興趣的讀者也可以自己嘗試證明一下為什麼這個密碼體系是對的。

RSA密碼的簡單例子

令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3(3與20互質)，則e×d≡1 mod f(n)，即3×d≡1 mod 20，這時可以取d=7，滿足e×d≡1 mod f(n)。這時公鑰為：KU =(e,n)=(3,33)，私鑰為：KR =(d, n)=(7,33)。

我們可以用這套密碼體系來傳輸英文字母，用字母的順序對應的數字來代表該字母。比如如果我們要傳輸字母y，可以這樣進行：字母y在字母表中的序號是25，就用25來代替y，通過加密計算C≡M^e(mod n)≡25^3(mod 33) = 15625(mod 33)=16。你可以將16傳給收信息的人，收信息的人收到16後，用D=C^d(mod n)來解密，具體計算是D=C^d(mod n) = 16 ^7(mod 33) = 268435456(mod 33) = 25，這就是y對應的序號，因此解密過程成功。

作者曾經設計的一個帳號體系也用到了素數的知識，原理跟上面的RSA比較類似，大致意識是先確定帳號的容量m ，即這個帳號系統一共支持多少個帳號，找一個素數p與m互質，找另個一個素數q，滿足 p*q mod m =1(我的這個方法不要求p是素數，只要跟m互質就可以了，當然如果p是素數，只要不是m的因子，是一定滿足跟m互質的條件的)。

我的這個方法設計非常精巧，也比較簡單，它最大的價值是競爭對手通過註冊幾個帳號是無法猜測出帳號的生成規律的，從而無法知道你的產品有多少用戶。下面我們來講講這個方法的具體實現原理。

每個用戶根據他註冊的次序給他賦予一個整數值k，即這個用戶是第k個註冊的，採用下面圖2的算法獲得該用戶的帳號(即後面的u1、u2、u3等等)。同時我們可以採用圖3的算法根據用戶的帳號獲得用戶是第幾個註冊的用戶。下面a的目的是為了讓所有用戶帳號位數一樣，比如如果a取9999999(9百99萬9999)，m取90000000(9千萬)，那麼用戶的帳號範圍就是10000000(1千萬)到99999999(9999萬9999)。大家可以看到這裡面生成帳號的過程類似RSA的加密過程，從帳號獲得用戶註冊順序的過程類似RSA的解密過程。

圖2：用戶帳號生成算法(類似於RSA的加

圖3：從用戶帳號獲得用戶的序號(類似於

素數在人類生活和自然界中的應用應該還非常多，等待聰明的人類來挖掘和探索。有興趣的讀者也可以結合素數的性質多思考，看是否能夠找到素數的巧妙應用。

最後我們從一個新的角度來看待素數，如果對大學線性代數忘光的讀者可以忽略下面的講解。每個自然數n都可以表示為若干個素數的乘積(見下面公式，這裡k是一共不同的素數個數，t_k 是這個素數在n的因子中出現的次數)，如果將素數按照從小到大排序，這種表示是唯一的。

因此，素數在自然數中的價值有點像向量空間的基(向量空間中是加法，上式是乘法，本質是一樣的，只要將上式兩邊取對數就變成了加法了)。如果把全體自然數想像成一個向量空間，素數就是這個空間的基，所有自然數都可以由素數全體組成的基底表示出來，只不過素數基底有無窮多個。任何一個自然數都可以看成由有限個基底張成的向量空間中的一個點。

參考文獻