2.1數(shù)論2.2群環(huán)域2.3算法復(fù)雜度理論2.4公鑰密碼學(xué)2.5信息論2.6概率論第2章物聯(lián)網(wǎng)信息安全的數(shù)學(xué)基礎(chǔ)

2.1數(shù)論

數(shù)論是研究整數(shù)性質(zhì)的一門理論。素數(shù)是組成整數(shù)的基本元素，數(shù)論的本質(zhì)是對素數(shù)性質(zhì)的研究。人們對于數(shù)論的研究非常早，數(shù)論幾乎和平面幾何有著同樣悠久的歷史。根據(jù)研究方法，可以將數(shù)論分為初等數(shù)論和高等數(shù)論。2.1.1整除

整數(shù)集對于加法、減法和乘法三種運算都是封閉的，但對于除法運算是不封閉的，為此引進整除的概念。

定義2-1

設(shè)a，b∈Z，b?≠

0，如果存在q∈Z，使得等式a?=?bq成立，那么稱b整除a或a被b整除，記作：b|a，此時b被稱為a的約數(shù)，a被稱為b的倍數(shù)。

如果不存在滿足等式a?=?bq的整數(shù)q，那么稱b不能整除a或a不能被b整除，記作：b

a。關(guān)于整除，有如下幾個簡單的性質(zhì)。

設(shè)a，b，c∈Z，b?≠

0，c?≠

0，則有：

(1)如果c|b，b|a，那么c|a；

(2)如果b|a，那么bc|ac，反之亦真；

(3)如果c|a，c|b，那么，對于任意m，n∈Z，有c|(ma?+?nb)；

(4)如果b|a，a≠0，那么|b|≤|a|；

(5)如果b|a，a|b，那么|b|

=

|a|。

定理2-1(帶余除法)設(shè)a，b∈Z，b?≠

0，則存在q，r∈Z，使得a?=?bq?+?r，0≤r<|b|，并且q，r是唯一的。

證明存在性。當(dāng)b|a時，取q?=?a/b，r?=

0即可。

當(dāng)b

a時，考慮集合E?=

{a－bk|k∈Z}，易知E中有正整數(shù)，因此E中有最小正整數(shù)，設(shè)為r?=?a－bk>0，下證r?<

|b|。

因為b

a，所以r?≠

|b|，若r>|b|，則存在r′=r－|b|>0，又r′∈E，故與r的最小性矛盾，從而存在q，r∈Z，使得a=bq+r，0≤r<|b|。

唯一性。設(shè)另有q′，r′∈Z，使得a?=?bq′+?r′，0≤r′<|b|，則b(q－q′)=r′－r，于是b|(r′－r)，但由于0≤|r′－r|<|b|，故r′－r=0，即r=r′，從而q=q′。

定義2-2

等式a?=?bq+r，0≤r<|b|中的整數(shù)q稱為a被b除所得的(不完全)商，整數(shù)r稱為a被b除所得的余數(shù)。

例2-1

設(shè)b?=?15，則

當(dāng)a?=?255時，a?=?17b?+?0，故q?=?17，r?=?0；

當(dāng)a?=?417時，a?=?27b?+?12，故q?=?27，r?=?12；

當(dāng)a?=?-81時，a?=?－6b?+?9，故q?=?－6，r?=?9。2.1.2最大公約數(shù)

定義2-3

最大公約數(shù)：設(shè)a，b是兩個整數(shù)，若整數(shù)d滿足d|a并且d|b，則稱d為a，b的一個公約數(shù)；公約數(shù)中最大的一個稱為最大公約數(shù)，記作：gcd(a，b)，可簡記為(a，b)。

若gcd(a，b)?=?1，則稱a，b互素。

最大公約數(shù)是數(shù)論中的一個重要概念，迄今為止有多種求最大公約數(shù)的算法，其中最為著名的是由古希臘學(xué)者歐幾里得提出的輾轉(zhuǎn)相除法，又稱為歐幾里德算法(Euclideanalgorithm)，是目前已知的最古老的算法。輾轉(zhuǎn)相除法是現(xiàn)代數(shù)論中的基本工具，有很多重要的應(yīng)用，它是RSA算法(一種在電子商務(wù)中廣泛使用的公鑰加密算法)的重要部分。輾轉(zhuǎn)相除法基于如下原理：兩個正整數(shù)a與b(a>b)的最大公約數(shù)等于其中較小的數(shù)b和兩數(shù)相除的余數(shù)r的最大公約數(shù)。令r0?=?a，r1?=?b，輾轉(zhuǎn)相除法過程如下：直到

其中

定理2-2

設(shè)兩數(shù)為a、b(b<a)，r?=?amodb，為a除以b以后的余數(shù)，k為a除以b的商，則gcd(a，b)?=?gcd(b，r)。

證明

第一步：令c?=?gcd(a，b)，則可設(shè)a?=?mc，b?=?nc。

第二步：根據(jù)前提可知r?=?a－kb?=mc－knc=(m－kn)c。

第三步：根據(jù)第二步結(jié)果可知c也是r的因數(shù)。

第四步：可以斷定m－kn與n互素。否則，可設(shè)m－kn=xd,n=yd，(d?>

1)，則m?=?kn?+?xd?=?kyd?+?xd?=?(ky?+?x)d，則a?=?mc?=?(ky?+?x)dc，b?=?nc?=?ycd，故a與b的最大公約數(shù)為cd，而非c，與前面結(jié)論矛盾。

從而可知gcd(b，r)?=?c，繼而gcd(a，b)?=?gcd(b，r)。

例2-2

利用輾轉(zhuǎn)相除法求4081與20723的最大公約數(shù)。

解根據(jù)輾轉(zhuǎn)相除法可以進行如下計算：

20723?=?4081?×?5?+?318

4081?=?318?×?12?+?265

318?=?265?×?1?+?53

265?=?53?×?5?+?0

所以gcd(4081，20?723)?=?53

例2-3

利用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)。

解根據(jù)輾轉(zhuǎn)相除法可以進行如下計算：

8251?=?6105?×?1?+?2146

6105?=?2146?×?2?+?1813

2146?=?1813?×?1?+?333

1813?=?333?×?5?+?148

333?=?148?×?2?+?37

148?=?37?×?4?+?0

所以37為8251與6105的最大公約數(shù)。輾轉(zhuǎn)相除法在計算機上很容易實現(xiàn)，可以使用迭代或者遞歸的策略。兩種策略對應(yīng)的C程序設(shè)計如下：

迭代策略：遞歸策略：2.1.3模運算與同余關(guān)系

定義2-4

模運算：如果a是一個整數(shù)，n是一個正整數(shù)，a除以n的余數(shù)r可以用a?(modn)表示，n稱為模，因此求余數(shù)的運算也被稱為模運算。在模運算的意義下，很容易定義如下幾種運算，設(shè)正整數(shù)p和整數(shù)a，b，則有

模p加法：(a?+?b)modp，其結(jié)果是a?+?b的算術(shù)和除以p的余數(shù)；

模p減法：(a－b)modp，其結(jié)果是a?-?b的算術(shù)差除以p的余數(shù)；

模p乘法：(a?×?b)modp，其結(jié)果是a?×?b的算術(shù)積除以p的余數(shù)。

定義2-5

同余關(guān)系：給定正整數(shù)m，如果整數(shù)a與b模m的余數(shù)相同，或者說a與b之差能被m整除，則稱a與b對于模m同余，或稱a與b同余，模為m，記為

a

b(modm)

很明顯同余關(guān)系是一個等價關(guān)系，具有如下三個基本性質(zhì)：

(1)自反性：a?≡?a(modm)。

(2)對稱性：若a?≡?b(modm)，則b?≡a(modm)。

(3)傳遞性：若a≡?b(modm)，b?≡?c(modm)，則

a≡?c(modm)。2.1.4中國剩余定理

定義2-6

一次同余方程：同余式

是含有一個未知量x的一次式，叫做一次同余方程。若存在

代入上述方程使兩邊同余，則c為上述方程的一個解。上述方程的兩個解c1和c2看做相同當(dāng)且僅當(dāng)

時。

定理2-3

設(shè)，則一次同余方程有且只有一個解。

對于如下一次同余方程組其中為大于1的整數(shù)，兩兩互素，

是任意給定的整數(shù)。如果帶入方程組使得同余式同時都成立，則c叫做上述方程組的解。上述方程組的兩個解c1和c2看做相同當(dāng)且僅當(dāng)時。

定理2-4

孫子定理：設(shè)上面一次同余方程組中大于1的整數(shù)兩兩互素，是任意給定的整數(shù)，則一次同余方程組有且只有一個解。2.1.5素數(shù)

定義2-7

素數(shù)：又稱質(zhì)數(shù)，指在一個大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。素數(shù)在數(shù)論中有著很重要的地位，是數(shù)論研究的中心內(nèi)容。我國著名數(shù)學(xué)家陳景潤研究的“哥德巴赫猜想”與“孿生素數(shù)猜想”都是關(guān)于素數(shù)的。

定義2-8

合數(shù)：是指除了1和它本身兩個因數(shù)外，還有其他因數(shù)的數(shù)。

由2?÷?1?=?2，2?÷?2?=?1，可知2的因數(shù)只有1和它本身2這兩個約數(shù)，所以2是素數(shù)。由于4?÷?1?=?4，4?÷?2?=?2，4?÷?4?=?1，很顯然，4的因數(shù)除了1和它本身4這兩個因數(shù)以外，還有因數(shù)2，所以4是合數(shù)。100以內(nèi)的質(zhì)數(shù)有2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，共有25個。

注：(1)?1既不是質(zhì)數(shù)也不是合數(shù)，因為它有且只有1這一個因數(shù)。

(2)?2和3是所有素數(shù)中唯一兩個連著的數(shù)。

(3)?2是唯一一個為偶數(shù)的素數(shù)。

定理2-5

素數(shù)的個數(shù)是無窮的。

關(guān)于素數(shù)的無窮性的證明有很多版本，最經(jīng)典的來自于歐幾里得。證明的思路是使用反證法。

證明假設(shè)質(zhì)數(shù)只有有限的n個，從小到大依次排列為p1，p2，…，pn，設(shè)N?=?p1?×?p2?×?…?×?pn，那么，N+1是不能被p1，p2，…，pn中的任意一個數(shù)整除的，所以N+1是素數(shù)。這與假設(shè)只有n個素數(shù)矛盾，所以可得出素數(shù)是無限多的。

關(guān)于素數(shù)在自然數(shù)中的分布規(guī)律，一直是數(shù)論學(xué)者研究的重點。一個個單獨來看，素數(shù)在自然數(shù)中的出現(xiàn)沒有什么規(guī)律?？墒强傮w地看，素數(shù)的個數(shù)是有規(guī)可循的。

素數(shù)定理對素數(shù)在自然數(shù)中的分布做出了一定的回答。

定理2-6

設(shè)是小于x的素數(shù)的個數(shù)，則,

當(dāng)時，比值。

該結(jié)果最早為德國數(shù)學(xué)家高斯發(fā)現(xiàn)，嚴格的證明來自于法國數(shù)學(xué)家哈達瑪。

定義2-9

歐拉函數(shù)：對于正整數(shù)n，將0，1，2，…，n－1中與n互素的整數(shù)的個數(shù)記作φ(n)，稱作歐拉函數(shù)。

例2-5

計算j(8)與j(10)。

解因為1，3，5，7均和8互素，所以j

(8)?=?4；

因為1，3，7，9均和10互素，所以j

(10)?=?4。

歐拉函數(shù)是數(shù)論中的一個重要函數(shù)，下面給出歐拉函數(shù)的一些基本性質(zhì)。

(1)若p是素數(shù)，則j

(p)?=?p－1。

(2)若n是素數(shù)p的k次冪，則j

(n)?=?(p－1)p(k－1)，因為除了p的倍數(shù)外都與p互素。

(3)歐拉函數(shù)是積性函數(shù)，若，則j

(mn)?=?j(m)j(n)。

根據(jù)性質(zhì)(2)和(3)，很容易根據(jù)數(shù)學(xué)歸納法得到性質(zhì)(4)：

(4)設(shè),為不同素數(shù)，ei≥1，則

(5)。

定理2-7

歐拉定理：若n與a為正整數(shù)，且n與a互素，即(a，n)?=?1，則

即與1在模n下同余，其中為歐拉函數(shù)。

例2-6

令a?=?3，n?=?5。比5小的正整數(shù)中與5互素的數(shù)有1、2、3和4，所以。3與5互素，則根據(jù)歐拉定理可知

另一方面34?=?81，而1(mod5)，與定理結(jié)果相符。

定理2-8

費馬小定理：假如p是一個質(zhì)數(shù)，而且(a，p)=1,則

定義2-10

整數(shù)模n的剩余類：對于一個給定的模數(shù)n，全體整數(shù)按照模n同余分成一些等價類，此時的等價類被稱為整數(shù)模n的剩余類。

定義2-11

完全剩余代表系：剩余類中的任意一個元素稱為該剩余類的一個代表。從每一個剩余類中任取一個代表，由這些代表組成的集合叫做整數(shù)模n的一個完全剩余代表系，用Zn表示。

注：很明顯，集合是模n的一個完全剩余代表系。

定義2-12

模n的既約剩余代表系：從完全剩余代表系中選出與n互素的代表，組成的集合叫做模n的既約剩余代表系，用

表示。

例2-7

n?=?10，，而。

定義2-13

a對模m的指數(shù)：在(a，m)?=?1時，a對模m的指數(shù)Ordm(a)為使成立的最小的正整數(shù)d。

定義2-14

本原元：根據(jù)歐拉定理可知Ordm(a)一定小于等于j(m)，若Ordm(a)?=?j(m)，則稱a是模m的本原元。

例2-8

設(shè)m?=?7，則。

(1)設(shè)a?=?2，由于，而3<6，所以2不是模7的一個本原元。

(2)設(shè)a?=?3，由于，，

，，，,因此有，所以3是模7的一個本原元。

2.2群環(huán)域

2.2.1群論

在數(shù)學(xué)中，群是一種代數(shù)結(jié)構(gòu)，由一個集合以及一個二元運算組成。例如整數(shù)集合上賦予加法運算就形成一個整數(shù)加群。一個群必須滿足一些被稱為“群公理”的條件，也就是封閉性、結(jié)合律、單位元和逆元。很多熟知的數(shù)學(xué)結(jié)構(gòu)比如數(shù)系統(tǒng)都遵從這些公理。

定義2-15

代數(shù)運算：設(shè)A是一個非空集合。任意一個由

到A的映射就稱為定義在A上的一個代數(shù)運算。

群有許多等價定義，本書引用聶靈沼和丁石孫合著的《代數(shù)學(xué)引論》中的定義。

定義2-16

群：設(shè)G是一個非空集合，a、b為其中的元素，如果在G上定義了一個代數(shù)運算，稱為乘法，記作ab(或稱為加法，記為a+b)，而且它滿足以下條件，那么稱G為一個群：

(1)對于G中任意元素a、b、c，有(ab)c?=?a(bc)(結(jié)合律)；

(2)?G中存在一個元素e，對G中任意元素a有ea?=?a；

(3)在G中，對于任意元素a都存在一個元素b使ba?=?e。

例2-9

全體非零實數(shù)對于通常的乘法構(gòu)成一個群，全體正實數(shù)對于通常的乘法構(gòu)成一個群，全體整數(shù)對于通常的加法構(gòu)成一個群。

設(shè)G為一個群，則它有如下基本性質(zhì)：

(1)?a、b、e∈G，如果ba=e，則ab=e；

(2)如果對所有的，有ea=a，那么也有ae=a，對所有的。

(3)?G中存在唯一的元素e，對所有的，都有

；

(4)對于群G中的任意元素a有唯一的元素b，使；

(5)對于群G中任意元素a、b，方程ax=b在G中有唯一解。

定義2-17

子群：如果群G的非空集合H對于G的運算也成一個群，那么H稱為G的一個子群。

例2-10

整數(shù)加群：(Z，?+?)是一個生成周期為無限的循環(huán)群。

分析：這個群的單位元素是0，且如果，則它的逆元素為－a。該群的生成元素為1，因為對任意一個正整數(shù)m均有，對于0有，對于任意負整數(shù)－m均有,

所以(Z，+)是由1所生成的群，且其周期為無限。2.2.2環(huán)理論

定義2-19

設(shè)L是一非空集合，a，b為L中的元素，在L上定義了兩個代數(shù)運算，一個叫加法，記為a+b，一個叫乘法，記為ab，如果滿足以下條件，則稱L為環(huán)：

(1)?L對于加法構(gòu)成一個交換群；

(2)乘法的結(jié)合律：對L中任意的元素a、b、c，有(ab)c=a(bc)；

(3)乘法對于加法的分配律:對L中任意的元素a、b、c,有

例2-11

全體整數(shù)集合，在其上賦予通常的加法和乘法運算，則構(gòu)成一個環(huán)，稱為整數(shù)環(huán)。環(huán)的基本性質(zhì)如下：

(1)用0代表環(huán)中加法群的零元素，則對于任意，有成立；

(2)對于任意，有

(3)對任意整數(shù)n、m，任意a，b

L，有

(4)對于正整數(shù)n、m，有

定理2-9

每個有限域的階必須為素數(shù)的冪。

定理2-10

對于任意素數(shù)p與正整數(shù)n，存在pn階域，記為GF(pn)。當(dāng)n=1時，有限域GF(p)也稱為素數(shù)域。

在密碼學(xué)中，最常見的域一般為素數(shù)域GF(p)或階為2m的域GF(2m)。2.2.4離散對數(shù)

為定義離散對數(shù)，首先定義一個素數(shù)p的原根，為其各次冪產(chǎn)生從1到p－1的所有整數(shù)根，也就是說，如果a是素數(shù)p的一個原根，那么數(shù)值

amodp，a2modp，…，ap-1modp

是各不相同的整數(shù)，并且以某種排列方式組成了從1到p-1的所有整數(shù)。

對于一個整數(shù)b和素數(shù)p的一個原根a，可以找到唯一的指數(shù)i，使得

b?=?aimodp，其中0≤i≤p－1

指數(shù)i稱為b的以a為基數(shù)的模p的離散對數(shù)。

2.3算法復(fù)雜度理論

算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度。時間復(fù)雜度是執(zhí)行算法所需要的計算工作量的量度；而空間復(fù)雜度是執(zhí)行這個算法所需要的內(nèi)存空間的量度。2.3.1時間復(fù)雜度

一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機運行測試之后才能知道?，F(xiàn)實中不可能也沒有必要對每個算法都上機測試其花費的具體時間。2.3.2空間復(fù)雜度

一個算法所需的存儲空間用f(n)表示，n表示問題的規(guī)模，記S(n)=O(f(n))，表示算法的空間復(fù)雜度。2.3.3圖靈機

1．基本思想

圖靈的基本思想是用機器來模擬人們用紙筆進行數(shù)學(xué)運算的過程，他把這樣的過程看做下列兩種簡單的動作：

(1)在紙上寫上或擦除某個符號；

(2)把注意力從紙的一個位置移動到另一個位置。

3．停機問題

停機問題(haltingproblem)是目前邏輯數(shù)學(xué)的焦點，是第三次數(shù)學(xué)危機的解決方案。其本質(zhì)問題是：給定一個圖靈機T和一個任意語言集合S，T是否會最終停機于每一個。其意義類似于可確定語言。顯然任意有限S是可判定性的，可數(shù)的(countable)?S也是可停機的。

4．圖靈機的變體

圖靈機有很多變種，但可以證明這些變種的計算能力都是等價的，即它們識別同樣的語言類。證明兩個計算模型A和B的計算能力等價的基本思想是：用A和B相互模擬，若A可模擬B且B可模擬A，則它們的計算能力等價。注意這里我們暫時不考慮計算的效率，只考慮計算的理論“可行性”。

5．非確定型圖靈機

如果不加特殊說明，通常所說的圖靈機都是確定型圖靈機。

非確定型圖靈機和確定型圖靈機的不同之處在于，在計算的每一時刻，根據(jù)當(dāng)前狀態(tài)和讀寫頭所讀的符號，機器存在多種狀態(tài)轉(zhuǎn)移方案，機器將任意地選擇其中一種方案繼續(xù)運作，直到最后停機為止。具體而言，其狀態(tài)轉(zhuǎn)移函數(shù)為其中：Q是狀態(tài)集合，是帶字母表，L、R分別表示讀寫頭向左和向右移動，符號2A表示集合A的冪集，即

6．P與NP問題

復(fù)雜度類P即為所有可以由一個確定型圖靈機在多項式表達的時間內(nèi)解決的問題；類NP為由所有可以在多項式表達的時間內(nèi)驗證解是否正確的決定問題組成，或者等效地說，那些解可以在非確定型圖靈機上在多項式表達的時間內(nèi)找出的問題的集合。

2.4公?鑰?密?碼?學(xué)

2.4.1基本概念

公鑰密碼學(xué)，又稱非對稱鑰匙密碼學(xué)，相對于對稱鑰匙密碼學(xué)，其最大的特點在于加密和解密使用不同的鑰匙。在對稱鑰匙密碼學(xué)中，加密和解密使用相同的鑰匙，也許對不同的信息使用不同的鑰匙，但都面臨鑰匙管理的難題。由于每對通信方都必須使用異于其他組的鑰匙，當(dāng)網(wǎng)絡(luò)成員的數(shù)量增加時，鑰匙數(shù)量成二次方增加。2.4.2RSA算法

1978年，MIT的RonRivest、AdiShamir和LenAdleman提出了公鑰加密算法RSA。RSA取名來自開發(fā)者的名字。RSA是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的所有密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標準。RSA算法基于一個十分簡單的數(shù)論事實：將兩個大素數(shù)相乘十分容易，但想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。假設(shè)Alice想要通過一個不可靠的媒體接收Bob的一條私人信息，她可以用以下的方式來產(chǎn)生一個公鑰和一個私鑰：

(1)隨意選擇兩個大的素數(shù)p和q，p不等于q，計算N=pq；

(2)根據(jù)歐拉函數(shù)，求得r=j(n)=j(p)j(q)=(p－1)(q－1)；

(3)選擇一個小于r的整數(shù)e，求得e關(guān)于模r的模反元素，命名為d(模反元素存在，當(dāng)且僅當(dāng)e與r互質(zhì)時)；

(4)將p和q的記錄銷毀。

(N，e)是公鑰，(N，d)是私鑰。Alice將她的公鑰(N，e)傳給Bob，而將她的私鑰(N，d)藏起來。加密消息：

假設(shè)Bob想給Alice送一個消息m，他知道Alice產(chǎn)生的N和e，使用事先與Alice約好的格式將m轉(zhuǎn)換為一個小于N的整數(shù)n，比如他可以將每一個字轉(zhuǎn)換為這個字的Unicode碼，然后將這些數(shù)字連在一起組成一串?dāng)?shù)字。假如他的信息非常長的話，他可以將這個信息分為幾段，然后將每一段轉(zhuǎn)換為n，用下面這個公式他可以將n加密為c：

計算c并不復(fù)雜。Bob算出c后就可以將它傳遞給Alice。解密消息：

Alice得到Bob的消息c后就可以利用她的密鑰d來解碼。她可以用以下這個公式來將c轉(zhuǎn)換為n：

得到n后，她可以將原來的信息m重新復(fù)原。

解碼的原理是：由費馬小定理可證明(因為p和q是素數(shù))

這說明(p和q互素)2.4.3單向陷門函數(shù)

定義2-23

單向函數(shù)：

一函數(shù)f若滿足下列兩個條件，則稱f為單向函數(shù)：

(1)對于所有屬于f定義域的任一x，可以很容易計算f(x)?=?y；

(2)對于幾乎所有屬于f值域的任一y，在計算上不可能(ComputationallyInfeasible)求出x，使得y?=?f(x)。

定義2-24

單向陷門函數(shù)：

(1)正向計算容易。給定x、k1，計算是容易的；

(2)反向計算可行，但要知道k2。給定y與k2，計算

是容易的；

(3)不知道k2，反向計算不可行。即給定y，不知道k2，計算x是不可行的，將k2稱為陷門信息。常見的單向陷門函數(shù)有以下幾種。

1．大整數(shù)分解

已知兩個大素數(shù)p和q，求n=pq只需要一次乘法，但若由n求出p和q，則是幾千年來數(shù)論學(xué)者的攻克對象。當(dāng)n很大時，則非常困難。已有的大整數(shù)分解的算法有試除法、二次篩選法、數(shù)域篩選法等。迄今為止，關(guān)于大整數(shù)分解尚未發(fā)現(xiàn)快速算法。

2．離散對數(shù)

設(shè)p是一個素數(shù)，是其生成元，已知，求

，稱為在模運算意義下的冪指數(shù)運算。但是，反過來，若成立，已知y求x的問題稱為在模運算意義下的離散對數(shù)問題(DLP)。

3．多項式求根

有限域GF(p)上的一個多項式,

當(dāng)給定時，易于求y。反之，已知

，求解x，需對高次方程求根。當(dāng)n、p很大時很難求解。

4．背包問題

已知向量，ai為正整數(shù)，給定向量

，，求和是容易的。但反過來，已知y和A，求x非常困難，稱這個問題為背包問題。背包問題用窮舉法有2n種可能，當(dāng)n很大時，求解相當(dāng)困難，已證明這是一個非多項式時間可解的問題。

5．二次剩余問題

設(shè)n為正整數(shù)，若存在整數(shù)a，滿足(a,n)=1，且x2=amodn有解，則稱a為模n的二次剩余，否則a稱為模n的二次非剩余，用QRn表示所有模n的二次剩余集合。給定正奇合數(shù)n，取

x=1,2,…,n－1，計算x2modn可得所有模n的二次剩余集合。但是，反過來，給定奇合數(shù)n和整數(shù)a，判定a是否是模n的二次剩余是困難的。

2.5信息論

定義2-25

設(shè)一個離散隨機變量，令xi出現(xiàn)的概率為P(xi)≥0，1≤i≤n，且，事件xi所包含的信息定義為

定義2-26

將集合X中事件所包含的信息量統(tǒng)計平均，則平均值

稱為集合X的熵。式中采用以2為底的對數(shù)運算，信息的單位為比特(bit)。集合X和Y的聯(lián)合熵定義為

集合X相對于事件的條件熵定義為集合X相對于集合Y的條件熵定義為

定理2-110≤H(X)≤lbn。當(dāng)且僅當(dāng)對某一i有p(xi)=1，對其他的時，有p(xj)?=?0，H(X)=0；當(dāng)且僅當(dāng)對一切1≤i≤n，有時，H(X)=lb?n。

定理2-12

推論若H(X|Y)≤H(X)，當(dāng)且僅當(dāng)X與Y相互統(tǒng)計獨立時，等號成立。

2.6概率論

2.6.1概率論的基本概念

定義2-27

隨機試驗：隨機現(xiàn)象是相對于決定性現(xiàn)象而言的，通常在概率論中把符合下面三個特點的試驗叫做隨機試驗：

(1)每次試驗的可能結(jié)果不止一個，并且能事先明確試驗的所有可能結(jié)果；

(2)進行一次試驗之前無法確定哪一個結(jié)果會出現(xiàn)；

(3)可以在同一條件下重復(fù)進行試驗。

定義2-28

單位事件：是在一次隨機試驗中可能發(fā)生的不能再細分的結(jié)果，又被稱為基本事件。

定義2-29

事件空間：隨機試驗所有可能發(fā)生的單位事件的集合，又稱為樣本空間。

定義2-30

隨機事件：是事件空間S的子集，它由事件空間S中的單位元素構(gòu)成。

定義2-31

設(shè)隨機事件的樣本空間為Ω，對于Ω中的每一個事件A，都有實函數(shù)P(A)，滿足：

(1)非負性：P(A)≥0；

(2)規(guī)范性：P(Ω)?=?1；

(3)可加性：對n個兩兩互斥事件A1，…，An有

任意一個滿足上述條件的函數(shù)P都可以作為樣本空間Ω的概率函數(shù)，稱函數(shù)值P(A)為Ω中事件A的概率。2.6.2基本性質(zhì)

事件與集合的性質(zhì)非常相似，所以很容易理解下面的性質(zhì)。

(1)互補原則：定義一個事件的補事件為，則。

(2)不可能事件的概率為零：。

(3)如果事件A1,A2,…,An中的任意兩者不相交，則和事件的概率等于單個事件的概率之和，即

(4)?。

(5)加法法則：對于事件空間中的任意兩個事件A和B都有

(6)乘法法則：事件A與B同時發(fā)生的概率為

(7)無關(guān)事件乘法法則：兩個不相關(guān)聯(lián)