大家在小學(xué)就學(xué)過(guò)素?cái)?shù)了，素?cái)?shù)也叫質(zhì)數(shù)，就是除了1和自身之外沒(méi)有其他約數(shù)(也叫因數(shù)) 的自然數(shù)，比如2、3、5、7、11等都是素?cái)?shù)，而4、6、8、9就不是(這種數(shù)叫做合數(shù))。回顧了素?cái)?shù)的概念后，下面我們來(lái)聊聊與素?cái)?shù)有關(guān)的有趣話題。
2是最小的素?cái)?shù)，也是唯一的偶素?cái)?shù)，2在所有素?cái)?shù)中的地位和價(jià)值是非常獨(dú)特的，我們已經(jīng)在《你可能不知道的數(shù)字2》中進(jìn)行了比較詳細(xì)的介紹。
根據(jù)素?cái)?shù)的定義和性質(zhì)，任何一個(gè)自然數(shù)都可以分解為若干個(gè)素?cái)?shù)的乘積。素?cái)?shù)的個(gè)數(shù)是無(wú)限多的，歐幾里得在《幾何原本》中給出了一個(gè)非常經(jīng)典的反證法證明，感興趣的讀者可以看參考文獻(xiàn)1了解這個(gè)證明過(guò)程。素?cái)?shù)有非常多有意思的性質(zhì)和命題，有些命題比較簡(jiǎn)單，很容易證明，比如剛剛提到的素?cái)?shù)個(gè)數(shù)是無(wú)限多的。有很多卻非常困難，幾百年以來(lái)，都沒(méi)有被世界的數(shù)學(xué)家解決，這其中最出名的要數(shù)哥德巴赫猜想了。哥德巴赫猜想是說(shuō)，任何大于等于4的偶數(shù)，都可以表示為兩個(gè)素?cái)?shù)之和。目前關(guān)于這一命題最好的結(jié)果是我國(guó)知名數(shù)學(xué)家陳景潤(rùn)的結(jié)論，陳景潤(rùn)證明了：一個(gè)充分大的偶數(shù)必定可以寫(xiě)成一個(gè)素?cái)?shù)加上一個(gè)最多由2個(gè)質(zhì)因子所組成的合數(shù)。
上面是素?cái)?shù)基礎(chǔ)知識(shí)的介紹，看起來(lái)素?cái)?shù)是數(shù)學(xué)家研究的話題，其實(shí)不然，素?cái)?shù)與我們的生活密切相關(guān)，素?cái)?shù)的如下3個(gè)性質(zhì)是非常重要的。
- 非常大的整數(shù)是難以分解為素因子的乘積的，需要非常大的計(jì)算量；
- 素?cái)?shù)沒(méi)有1和本身之外的因子，素?cái)?shù)和與它互質(zhì)的數(shù)的最小公倍數(shù)是它們的乘積；
- 素?cái)?shù)在自然數(shù)中的分布是沒(méi)有什么規(guī)律的；
下面我們來(lái)談?wù)勗谧匀唤绾腿祟?lèi)生活中素?cái)?shù)的價(jià)值，這些價(jià)值的發(fā)揮基本都與上面素?cái)?shù)的3個(gè)特性有關(guān)。
在汽車(chē)變速箱齒輪的設(shè)計(jì)上，相鄰的兩個(gè)大小齒輪齒數(shù)設(shè)計(jì)成素?cái)?shù)，以增加兩個(gè)齒輪內(nèi)兩個(gè)相同的齒相遇嚙合次數(shù)的最小公倍數(shù)(即是這兩個(gè)齒輪齒數(shù)的乘積，兩個(gè)素?cái)?shù)的最小公倍數(shù)就是它們的乘積)，這可以防止有的齒經(jīng)常和另一個(gè)齒輪的某一齒單一接觸(特別是當(dāng)這個(gè)齒設(shè)計(jì)有一些小的缺陷時(shí)，任何機(jī)械工程都是有一些小誤差的)，可增強(qiáng)耐用度、減少故障。
圖1：齒輪之間的咬合，如果每個(gè)齒輪是素?cái)?shù)個(gè)齒，會(huì)更加安全耐用
上述齒輪齒數(shù)的設(shè)計(jì)其實(shí)是用到了素?cái)?shù)與它互質(zhì)的數(shù)的最小公倍數(shù)是它們的乘積這一性質(zhì)，這一性質(zhì)在生物學(xué)上也有比較有意思的現(xiàn)象。大家熟知的知了，學(xué)名叫做蟬，在自然界進(jìn)化出了非常特別的繁殖周期，目前發(fā)現(xiàn)的有13年蟬、17年蟬等(讀者可以看參考文獻(xiàn)了解更多細(xì)節(jié))，也就是它們的幼蟲(chóng)需要在地底下分別生活13年、17年才能破土而出，蟬出土后的生命一般只有2個(gè)月左右，為了綻放兩個(gè)月的生命，它們需要在毫無(wú)光亮的地底下生活13年、17年，生命是多么的神奇和偉大啊！
13年蟬、17年蟬之所以進(jìn)化出這種奇特的繁殖周期，是為了逃避天敵的侵害并安全延續(xù)種群，因而演化出一個(gè)漫長(zhǎng)而隱秘的素?cái)?shù)生命周期(13、17都是素?cái)?shù))。當(dāng)蟬的繁殖周期是13、17年時(shí)，蟬與它的天敵繁殖周期碰到一起就需要經(jīng)過(guò)它們繁殖周期的乘積這么多年，而如果他們的繁殖周期碰到一起的話，天敵的幼蟲(chóng)就會(huì)以蟬的幼蟲(chóng)為食，對(duì)蟬的種群延續(xù)是很不利的。蟬進(jìn)化出這么奇怪的繁殖周期就是為了避免天敵的傷害，這里我們進(jìn)一步看到了生物進(jìn)化的魅力。
除了蟬以外，在害蟲(chóng)的生物生長(zhǎng)周期與殺蟲(chóng)劑使用之間的關(guān)系上，殺蟲(chóng)劑的質(zhì)數(shù)次使用的有效性也得到了科學(xué)的證明：實(shí)驗(yàn)表明，質(zhì)數(shù)次數(shù)地使用殺蟲(chóng)劑是最合理的，并且需要在害蟲(chóng)繁殖的高潮期使用，這樣害蟲(chóng)很難產(chǎn)生抗藥性。這樣使用主要是為了將相鄰批次的繁殖期的害蟲(chóng)都被殺蟲(chóng)劑殺掉，避免了不同次代的害蟲(chóng)之間的交配繁殖。
在軍事領(lǐng)域，以質(zhì)數(shù)形式發(fā)出的無(wú)規(guī)律變化的導(dǎo)彈和魚(yú)雷可以使敵人不易攔截，這是利用了素?cái)?shù)分布的無(wú)規(guī)律性。
素?cái)?shù)在我們?nèi)粘Ｉ钪幸卜浅Ｓ杏茫蠹颐總€(gè)人都有很多賬號(hào)和密碼，素?cái)?shù)與他們都有關(guān)系。素?cái)?shù)與我們生活最相關(guān)的應(yīng)用要數(shù)在密碼學(xué)上的應(yīng)用了。現(xiàn)在比較安全的密碼很多都是基于素?cái)?shù)理論構(gòu)建的，它主要利用了將一個(gè)非常大的整數(shù)分解為素因子是一件非常困難的事情這一特性。基于素?cái)?shù)構(gòu)建的復(fù)雜密碼體系，在有限的時(shí)間和現(xiàn)有的計(jì)算資源下基本是無(wú)法破解的。
我們知道，任何一個(gè)自然數(shù)都可以分解為素?cái)?shù)的乘積，如果不計(jì)因數(shù)的次序，分解形式是唯一的。這叫做算術(shù)基本定理。但是將一個(gè)大整數(shù)分解卻沒(méi)有一個(gè)簡(jiǎn)單易用的好方法，只能用較小的素?cái)?shù)一個(gè)一個(gè)去試除，耗時(shí)極大。如果用計(jì)算機(jī)來(lái)分解一個(gè)100位的數(shù)字，所花的時(shí)間要以萬(wàn)年計(jì)。可是將兩個(gè)100位的數(shù)字相乘，對(duì)計(jì)算機(jī)卻十分容易。美國(guó)數(shù)學(xué)家就利用了這一點(diǎn)發(fā)明了編制容易而破譯難的密碼體系，這種編碼方式以三位發(fā)明者姓氏的首字母命名為RSA碼。下面我們就來(lái)簡(jiǎn)單說(shuō)明這種密碼是怎么巧妙利用素?cái)?shù)來(lái)構(gòu)建的。
RSA密碼的加密解密算法
下面講解RSA密碼的算法原理，我們可以通過(guò)如下8步來(lái)進(jìn)行加密和解密，具體如下：
（1）選擇一對(duì)不同的、足夠大的素?cái)?shù)p、q (p, q嚴(yán)加保密，不讓任何人知道，p、q越大，也越難破解)；
（2）計(jì)算n=p*q；
（3）計(jì)算f(n)=(p-1)*(q-1) ；
（4）找一個(gè)與f(n)互質(zhì)的數(shù)e，滿(mǎn)足 1<e<f(n)；
（5）計(jì)算d，使得d*e ≡ 1 mod f(n)；
這里 ≡ 是數(shù)論中表示同余的符號(hào)。公式中 ≡ 符號(hào)的左邊必須和符號(hào)右邊同余，也就是兩邊模運(yùn)算結(jié)果相同。顯而易見(jiàn)，不管f(n)取什么值，符號(hào)右邊1 mod f(n)的結(jié)果都等于1；符號(hào)的左邊d與e的乘積取模運(yùn)算后的結(jié)果也必須等于1。這就需要計(jì)算出d的值，讓這個(gè)同余等式能夠成立，一般可以通過(guò)逐個(gè)嘗試的方法找到可行的d；
（6）公鑰KU=(e, n)(公鑰就是可以公開(kāi)的，大家都可以知道)，私鑰KR=(d,n)(私鑰需要自己保密，用于破解密碼用)；
（7）對(duì)于0至n-1之間的任意一個(gè)整數(shù)M，可以這樣加密：C≡M^e(mod n)(這里M^e是指M的e次方，下面類(lèi)似)，C就是需要傳輸?shù)男畔ⅲ瑢給到你想傳遞信息的人；
（8）接收人收到信息C后，通過(guò)計(jì)算D=C^d(mod n)，就獲得了原來(lái)的信息M，即D=M；
如果傳輸?shù)男畔⒑芏啵梢岳?、1、2、……、n-1 對(duì)信息進(jìn)行編碼(比如需要傳輸?shù)氖怯⑽膯卧~，可以對(duì)每一個(gè)字母編碼，可以根據(jù)字母順序編碼，a->1、b->2、c->3、以此類(lèi)推)。下面我們講個(gè)例子讓大家更好地理解上面的原理的正確性。對(duì)這個(gè)感興趣的讀者也可以自己嘗試證明一下為什么這個(gè)密碼體系是對(duì)的。
RSA密碼的簡(jiǎn)單例子
令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3(3與20互質(zhì))，則e×d≡1 mod f(n)，即3×d≡1 mod 20，這時(shí)可以取d=7，滿(mǎn)足e×d≡1 mod f(n)。這時(shí)公鑰為：KU =(e,n)=(3,33)，私鑰為：KR =(d, n)=(7,33)。
我們可以用這套密碼體系來(lái)傳輸英文字母，用字母的順序?qū)?yīng)的數(shù)字來(lái)代表該字母。比如如果我們要傳輸字母y，可以這樣進(jìn)行：字母y在字母表中的序號(hào)是25，就用25來(lái)代替y，通過(guò)加密計(jì)算C≡M^e(mod n)≡25^3(mod 33) = 15625(mod 33)=16。你可以將16傳給收信息的人，收信息的人收到16后，用D=C^d(mod n)來(lái)解密，具體計(jì)算是D=C^d(mod n) = 16 ^7(mod 33) = 268435456(mod 33) = 25，這就是y對(duì)應(yīng)的序號(hào)，因此解密過(guò)程成功。
作者曾經(jīng)設(shè)計(jì)的一個(gè)賬號(hào)體系也用到了素?cái)?shù)的知識(shí)，原理跟上面的RSA比較類(lèi)似，大致意識(shí)是先確定賬號(hào)的容量m ，即這個(gè)賬號(hào)系統(tǒng)一共支持多少個(gè)賬號(hào)，找一個(gè)素?cái)?shù)p與m互質(zhì)，找另個(gè)一個(gè)素?cái)?shù)q，滿(mǎn)足 p*q mod m =1(我的這個(gè)方法不要求p是素?cái)?shù)，只要跟m互質(zhì)就可以了，當(dāng)然如果p是素?cái)?shù)，只要不是m的因子，是一定滿(mǎn)足跟m互質(zhì)的條件的)。
我的這個(gè)方法設(shè)計(jì)非常精巧，也比較簡(jiǎn)單，它最大的價(jià)值是競(jìng)爭(zhēng)對(duì)手通過(guò)注冊(cè)幾個(gè)賬號(hào)是無(wú)法猜測(cè)出賬號(hào)的生成規(guī)律的，從而無(wú)法知道你的產(chǎn)品有多少用戶(hù)。下面我們來(lái)講講這個(gè)方法的具體實(shí)現(xiàn)原理。
每個(gè)用戶(hù)根據(jù)他注冊(cè)的次序給他賦予一個(gè)整數(shù)值k，即這個(gè)用戶(hù)是第k個(gè)注冊(cè)的，采用下面圖2的算法獲得該用戶(hù)的賬號(hào)(即后面的u1、u2、u3等等)。同時(shí)我們可以采用圖3的算法根據(jù)用戶(hù)的賬號(hào)獲得用戶(hù)是第幾個(gè)注冊(cè)的用戶(hù)。下面a的目的是為了讓所有用戶(hù)賬號(hào)位數(shù)一樣，比如如果a取9999999(9百99萬(wàn)9999)，m取90000000(9千萬(wàn))，那么用戶(hù)的賬號(hào)范圍就是10000000(1千萬(wàn))到99999999(9999萬(wàn)9999)。大家可以看到這里面生成賬號(hào)的過(guò)程類(lèi)似RSA的加密過(guò)程，從賬號(hào)獲得用戶(hù)注冊(cè)順序的過(guò)程類(lèi)似RSA的解密過(guò)程。
圖2：用戶(hù)賬號(hào)生成算法(類(lèi)似于RSA的加密過(guò)程)
圖3：從用戶(hù)賬號(hào)獲得用戶(hù)的序號(hào)(類(lèi)似于RSA的解密過(guò)程)
素?cái)?shù)在人類(lèi)生活和自然界中的應(yīng)用應(yīng)該還非常多，等待聰明的人類(lèi)來(lái)挖掘和探索。有興趣的讀者也可以結(jié)合素?cái)?shù)的性質(zhì)多思考，看是否能夠找到素?cái)?shù)的巧妙應(yīng)用。
最后我們從一個(gè)新的角度來(lái)看待素?cái)?shù)，如果對(duì)大學(xué)線性代數(shù)忘光的讀者可以忽略下面的講解。每個(gè)自然數(shù)n都可以表示為若干個(gè)素?cái)?shù)的乘積(見(jiàn)下面公式，這里k是一共不同的素?cái)?shù)個(gè)數(shù)，t_k是這個(gè)素?cái)?shù)在n的因子中出現(xiàn)的次數(shù))，如果將素?cái)?shù)按照從小到大排序，這種表示是唯一的。
因此，素?cái)?shù)在自然數(shù)中的價(jià)值有點(diǎn)像向量空間的基(向量空間中是加法，上式是乘法，本質(zhì)是一樣的，只要將上式兩邊取對(duì)數(shù)就變成了加法了)。如果把全體自然數(shù)想像成一個(gè)向量空間，素?cái)?shù)就是這個(gè)空間的基，所有自然數(shù)都可以由素?cái)?shù)全體組成的基底表示出來(lái)，只不過(guò)素?cái)?shù)基底有無(wú)窮多個(gè)。任何一個(gè)自然數(shù)都可以看成由有限個(gè)基底張成的向量空間中的一個(gè)點(diǎn)。
參考文獻(xiàn)
- [百度百科關(guān)于素?cái)?shù)的介紹] https://baike.baidu.com/item/質(zhì)數(shù)/263515?fromtitle=素?cái)?shù)&fromid=115069&fr=aladdin
- [周期蟬] https://baike.baidu.com/item/周期蟬/2666050
