新編密碼學(xué) 課件 第2章 基礎(chǔ)知識

2.1數(shù)論

2.2計算復(fù)雜性問題2.1數(shù)論在數(shù)學(xué)中,研究整數(shù)性質(zhì)的分支稱為數(shù)論。數(shù)論中的許多概念是設(shè)計公鑰密碼算法的基礎(chǔ),數(shù)論領(lǐng)域中的大整數(shù)分解、素性檢測、開方求根、求解不同模數(shù)的同余方程組等問題在公鑰密碼學(xué)中經(jīng)常遇到,同時它們也是數(shù)論中非常重要的內(nèi)容。2.1.1素數(shù)與互素1.整除與素數(shù)如果整數(shù)a,b,c之間存在關(guān)系a=b·c且b≠0,則稱b整除a或者a能被b整除,且b是a的因子或除數(shù),a是b的倍數(shù),記為b|a。整除有如下性質(zhì):性質(zhì)1a|a。性質(zhì)2如果a|1,則有a=±1。性質(zhì)3對于任何a≠0,則有a|0。性質(zhì)4如果a|b且b|a,那么a=±b。性質(zhì)5如果a|b且b|c,則有a|c。性質(zhì)6如果a|b且b|c,那么對所有的x,y∈?,有a|(bx+cy)(這里?表示整數(shù)集,下同)。根據(jù)整除的定義,這些性質(zhì)都是顯而易見的,在此不再證明。另外,在本書中,如不做特別說明,所有的量均取整數(shù)。如果p>1且只能被1和自身整除,則正整數(shù)p稱為素數(shù)或質(zhì)數(shù)。非素數(shù)的整數(shù)稱為合數(shù)。1既不是素數(shù),也不是合數(shù)。素數(shù)的一些基本結(jié)論如下:結(jié)論1素數(shù)有無窮多個。結(jié)論2設(shè)p是素數(shù),xi(i=1,2,…,n)是整數(shù),如果,則至少存在一個xi(i∈{1,2,…,n})能被p整除。結(jié)論3(素數(shù)定理)設(shè)x∈?,則不超過x的素數(shù)個數(shù)可近似地用

表示。結(jié)論4(算術(shù)基本定理)設(shè)2≤n∈?,則n可分解成素數(shù)冪的乘積:其中,pi(i=1,2,…,n)是互不相同的素數(shù),αi(i=1,2,…,n)是正整數(shù)。如果不計因子的順序,則上述因子分解式是唯一的。2.最大公因子與互素設(shè)a,b,c∈?,如果c|a且c|b,則稱c是a與b的公因子或公約數(shù)。如果d滿足下列條件,則稱正整數(shù)d是a與b的最大公因子或最大公約數(shù)。(1)d是a與b的公因子。(2)如果c也是a與b的公因子,則c必是d的因子?？梢?a與b的最大公因子就是a與b的公因子中最大的那一個,記為d=gcd(a,b)=max{c|{c|a且c|b}}。注:如果a和b全為0,則它們的公因子和最大公因子均無意義。如果a與b的最大公因子為1,即gcd(a,b)=1,則稱整數(shù)a與b互素。最大公因子有以下性質(zhì):性質(zhì)1任何不全為0的兩個整數(shù)的最大公因子存在且唯一。性質(zhì)2設(shè)整數(shù)a與b不全為0,則存在整數(shù)x和y,使得ax+by=gcd(a,b)。特別地,如果a與b互素,則存在整數(shù)x和y,使得ax+by=1。性質(zhì)3如果gcd(a,b)=d,性質(zhì)4如果gcd(a,x)=gcd(b,x)=1,那么gcd(ab,x)=1。性質(zhì)5如果c|(ab),且gcd(b,c)=1,那么c|a。以上性質(zhì)可由因子和素數(shù)的定義直接證明,并且上面關(guān)于因子和互素的概念與性質(zhì)都可以推廣到多個整數(shù)的情況。2.1.2同余與模運算1.帶余除法對于任意兩個正整數(shù)a和b,一定可以找到唯一確定的兩個整數(shù)k和r,滿足a=kb+r(0≤r<b),則k和r分別被稱為a除以b(或者b除a)的商和余數(shù),并把滿足這種規(guī)則的運算稱為帶余除法。顯然,在帶余除法中,,其中x表示不大于x的最大整數(shù),或者稱為x的下整數(shù)。若記a除以b的余數(shù)為amodb,則帶余除法可表示成:例如,若a=17,b=5,則a=3b+2,即

，r≡17mod5≡2。對于整數(shù)a<0,也可以類似地定義帶余除法和它的余數(shù),如-17mod5≡3。2.整數(shù)同余與模運算設(shè)a,b,n∈?且n>0,如果a和b除以n的余數(shù)相等,即amodn≡bmodn,則稱a與b模n同余,并將這種關(guān)系記為a≡bmodn,n稱為模數(shù),相應(yīng)地,amodn也可以稱為a模n的余數(shù)。例如,17≡2mod5,73≡27mod23。顯然,如果a與b模n同余,則必然有n(a-b),也可以寫成a-b=kn或a=kn+b,其中k∈?。由帶余除法的定義可知,任何整數(shù)a除以正整數(shù)n的余數(shù)一定在集合{0,1,2,…,n-1}中,結(jié)合整數(shù)同余的概念,所有整數(shù)根據(jù)模n同余關(guān)系可以分成n個集合,每個集合中的整數(shù)模n同余,將這樣的集合稱為模n同余類或剩余類,依次記為[0]n,[1]n,[2]n,…,[n-1]n,即[x]n={y|y∈?∧y≡xmodn},x∈{0,1,2,…,n-1}。如果從每個模n同余類中取一個數(shù)為代表,形成一個集合,則此集合稱為模n的完全剩余系,用?n表示。顯然,?n的最簡單表示就是集合{0,1,2,…,n-1},即?n={0,1,2,…,n-1}。綜上可知,amodn將任一整數(shù)a映射到?n={0,1,2,…,n-1}中,并且是唯一的數(shù),這個數(shù)就是a模n的余數(shù),所以可將amodn視作一種運算,并稱其為模運算。模運算有如下性質(zhì)(其中n>1):性質(zhì)1如果n(a-b),則a≡bmodn。性質(zhì)2模n同余關(guān)系是整數(shù)間的一種等價關(guān)系,它具有等價關(guān)系的3個基本性質(zhì):(1)自反性

對任意整數(shù)a,有a≡amodn。(2)對稱性

如果a≡bmodn,則b≡amodn。(3)傳遞性

如果a≡bmodn且b≡cmodn,則a≡cmodn。性質(zhì)3如果a≡bmodn且c≡dmodn,則a±c≡(b±d)modn,ac≡bdmodn。性質(zhì)4模運算具有普通運算的代數(shù)性質(zhì),即(amodn±bmodn)modn≡(a±b)modn(amodn×bmodn)modn≡(a×b)modn(a×b)modn±(a×c)modn≡[a×(b±c)]modn性質(zhì)5(加法消去律)如果(a+b)≡(a+c)modn,則b≡cmodn。性質(zhì)6(乘法消去律)如果ab≡acmodn且gcd(a,n)=1,則b≡cmodn。性質(zhì)7如果ac≡bdmodn,c≡dmodn且gcd(c,n)=1,則a≡bmodn。2.1.3歐拉定理1.歐拉函數(shù)設(shè)n∈?且n>1,將小于n且與n互素的正整數(shù)的個數(shù)稱為n的歐拉(Euler)函數(shù),記為φ(n)。例如,φ(5)=4,φ(6)=2。歐拉函數(shù)有如下性質(zhì):性質(zhì)1如果p為素數(shù),則有φ(p)=p-1。性質(zhì)2如果gcd(m,n)=1,則φ(mn)=φ(m)φ(n)。性質(zhì)3如果(其中,pi

為素數(shù),αi

為正整數(shù),i=1,2,…,k)。2.歐拉定理定理2.2(歐拉定理)設(shè)a,n∈?且n>1,如果gcd(a,n)=1,那么aφ(n)≡1modn。證明

記小于n且與n互素的全體正整數(shù)構(gòu)成的集合R={x1,x2,…,xφ(n)},這個集合也稱為模n的既約剩余系,那么對于集合中任一元素aximodn(i=1,2,…,φ(n)),由于所以gcd(axi,n)=1。加之a(chǎn)ximodn<n,故aximodn∈R,進(jìn)而aRmodn?R。又因為對于任意的xi,xj∈R且xi≠xj,都有aximodn≠axjmodn。否則,若aximodn=axjmodn,那么由于gcd(a,n)=1,根據(jù)消去律可得ximodn=xjmodn,即xi=xj,所以集合aRmodn中沒有相同的元素,因此aRmodn=R。令兩個集合的全體元素相乘,則有所以再由gcd(xi,n)=1(i=1,2,…,φ(n))和消去律可得

由歐拉定理可得如下推論:推論1若p為素數(shù)且gcd(a,p)=1,則有aφ(p)=ap-1≡1modp。這個結(jié)論又稱為費爾馬(Fermat)定理。推論2若gcd(a,n)=1,顯然有aφ(n)-1≡a-1modn,aφ(n)+1≡amodn;對于n=p為素數(shù)的情況,有ap≡amodp,ap-2≡a-1modn。推論3設(shè)n=pq且p和q為素數(shù),a∈?,如果gcd(a,n)=p或q,則同樣有aφ(n)+1≡amodn。根據(jù)歐拉定理,如果gcd(a,n)=1,則至少存在一個整數(shù)m滿足方程am≡1modn,例如m=φ(n)。稱滿足方程am≡1modn的最小正整數(shù)m為a模n的階。例如,若a=5,n=11,則有51≡5mod11,52≡3mod11,53≡4mod11,54≡9mod11,55≡1mod11,則5模11的階為5。如果a模n的階m=φ(n),則稱a為n的本原根或者本原元。顯然,5不是11的本原根。由本原根的定義和模運算的性質(zhì)可知,如果a是n的本原根,那么a,a2,…,aφ(n)在模n下互不相同且都與n互素;如果n=p為素數(shù),則有a,a2,…,ap-1在模p下互不相同且都與p互素,即并非所有的正整數(shù)都有本原根,且有本原根的整數(shù),其本原根也不一定唯一。只有以下形式的正整數(shù)才有本原根:其中,p為奇素數(shù),α為正整數(shù)。例如,7有兩個本原根,分別是3和52.1.4幾個有用的算法1.歐幾里得算法在2.1.2節(jié)中,我們給出了模運算下的乘法逆元概念,求模運算下的乘法逆元是數(shù)論中常用的一種技能。由歐拉定理,我們知道,若整數(shù)a與n互素,則1≡aφ(n)modn,那么a-1≡aφ(n)-1modn,但如果n不是素數(shù),則不容易求出φ(n),所以這種方法在多數(shù)情況下不適用?，F(xiàn)在求乘法逆元最有效的方法是歐幾里得算法?；镜臍W幾里得算法可以方便地求出兩個整數(shù)的最大公因子,擴展的歐幾里得算法不僅可以求兩個整數(shù)的最大公因子,在這兩個整數(shù)互素的情況下,還可以求出其中一個數(shù)模另一個數(shù)的乘法逆元。1)基本的歐幾里得算法歐幾里得(Euclid)算法基于一個基本事實:對任意兩個整數(shù)a和b(設(shè)a>b>0),有g(shù)cd(a,b)=gcd(b,amodb)。注:若其中有負(fù)整數(shù),則可以通過其絕對值來求它們的最大公因子;若其中一個為0,則最大公因子為非0的那一個;若兩個都為0,則最大公因子無意義。證明

對于任意兩個整數(shù)a和b,一定存在整數(shù)k,滿足a≡(kb+a)modb設(shè)d是a與b的任一公因子,故d|a且d|b,所以d|(a-kb),即d|(amodb)。因此,d是b與amodb的公因子。同理,若d是b與amodb的公因子,則d也是a與b的公因子。所以a與b的全部公因子和b與amodb的全部公因子完全相同,因此它們的最大公因子也相同,即gcd(a,b)=gcd(b,amodb)在計算兩個整數(shù)的最大公因子時,可以重復(fù)使用上面的結(jié)論,直到余數(shù)變?yōu)?,這個過程稱為輾轉(zhuǎn)相除。通過輾轉(zhuǎn)相除求最大公因子的過程可表示如下:其中,r0≡amodb,r1≡bmodr0,ri≡ri-2modri-1(i=2,3,…,n)。由于r0>r1>r2>…≥0且它們皆為整數(shù),所以上面的帶余除法在經(jīng)過有限步后余數(shù)必為0。最后,當(dāng)余數(shù)為0時,有g(shù)cd(rn,0)=rn。再倒推回來,可得rn=gcd(rn,0)=gcd(rn-1,rn)=gcd(rn-2,rn-1)=…=gcd(r0,r1)=gcd(b,r0)=gcd(a,b),即輾轉(zhuǎn)相除到余數(shù)為0時,其前一步的余數(shù)即為要求的最大公因子。歐

幾

里

得

算

法

就

是

使

用

輾

轉(zhuǎn)

相

除

法

求

兩

個

整

數(shù)

最

大

公

因

子

的

簡

化

過

程

。例

如,gcd(30,12)=gcd(12,6)=gcd(6,0)=6。歐幾里得算法描述如下(假定輸入的兩個整數(shù)a>b>0):2)擴展的歐幾里得算法基本的歐幾里得算法不僅可以求出兩個整數(shù)a和b的最大公因子gcd(a,b),而且還可以進(jìn)一步求出方程sa+tb=gcd(a,b)的一組整數(shù)解(注意s,t不唯一)。具體方法是將歐幾里算法倒推回去,由輾轉(zhuǎn)相除過程中的倒數(shù)第二行可得即gcd(a,b)可表示成rn-2和rn-1的整系數(shù)線性組合。再由輾轉(zhuǎn)相除過程中的倒數(shù)第三行可得代入式gcd(a,b)=rn=rn-2-rn-1kn,可得即gcd(a,b)可表示成rn-3和rn-2的整系數(shù)線性組合。如此下去,最終可將gcd(a,b)表示成a和b的整系數(shù)線性組合,即如

果a與b互

素,即gcd(a,b)=1,則

有1=sa+tb,所

以sa=1modb,因

此s=a-1modb。擴展的歐幾里得算法不僅能夠求出gcd(a,b),而且當(dāng)gcd(a,b)=1時,它還能求出a-1modb。擴展的歐幾里得算法描述如下所示。算法中,Q即為X3

除以Y3

的商,故X3-QY3

就是X3

除以Y3

的余數(shù)X3modY3。與基本的歐幾里得算法一樣,這里的X3與Y3

通過中間變量T3

輾轉(zhuǎn)相除,最終產(chǎn)生a與b的最大公因子gcd(a,b)。算法中的變量之間有如下關(guān)系:如果gcd(a,b)=1,則在最后一輪循環(huán)中Y3=1。因此,bY1+aY2=1,進(jìn)而aY2≡1modb,Y2≡a-1modb,或者bY1≡1moda,Y1≡b-1moda。2.快速指數(shù)算法在RSA等公鑰密碼算法中,經(jīng)常遇到大量的底數(shù)和指數(shù)均為大整數(shù)的模冪運算。如果按模冪運算的含義直接計算,一方面可能由于中間結(jié)果過大而超過計算機允許的整數(shù)取值范圍,另一方面其運算工作量也是讓人難以忍受的。要有效解決這個問題,可以從以下兩個方面著手:(1)利用模運算的性質(zhì),即其中,m=u+v。(2)提高指數(shù)運算的有效性。例如,通過計算出x,x2,x4,x8,x16,可以方便地組合出指數(shù)在1~31之間的任何一個整數(shù)次冪,并且最多只需4次乘法運算即得出答案。一般地,求am

可以通過如下快速指數(shù)算法完成,其中a和m是正整數(shù)。將m表示成二進(jìn)制的形式即因此，有所以因此,計算am

的快速指數(shù)算法如下:上面的算法中,變量c表示指數(shù)的變化情況,其終值是m;變量d表示相對于指數(shù)c的冪的變化情況,其終值就是所求的am

。其實,變量c完全可以去掉,但也可以通過c的值來判斷d是否達(dá)到最終結(jié)果am。3.素性檢測算法判定一個給定的整數(shù)是否為素數(shù)的問題被稱為素性檢測。目前,對于大整數(shù)的素性檢測問題還沒有簡單直接的通用方法,在這里介紹一個概率檢測算法。先介紹一個引理。引理2.1如果p是大于2的素數(shù),則方程x2≡1modp的解只有x≡±1modp。證明

由x2≡1modp得x2-1≡0modp所以(x+1)(x-1)≡0modp因此,有p(x+1),或p(x-1),或p(x+1)且p(x-1)。事實上,p(x+1)且p(x-1)是不可能的,如果p(x+1)與p(x-1)同時成立,則存在兩個整數(shù)s,t滿足x+1=spx-1=tp兩式相減,得到2=(s-t)p對大于2的素數(shù)p和整數(shù)s,t,這是不可能的。因此,只能有p|(x+1)或者p|(x-1)。由p(x+1)可得,x+1=kp,故x≡-1modp。同理,由p(x-1)可得x≡1modp。所以,如果p是大于2的素數(shù),則方程x2≡1modp的解只有x≡±1modp。此引理的逆否命題為:如果方程x2≡1modp存在非±1(模p)的解,則p不是大于2的素數(shù)。例如,32mod8≡1,所以8不是素數(shù)。上述引理的逆否命題就是著名的Miller-Rabin素性檢測算法的基本依據(jù)之一。下面給出Miller-Rabin素性檢測算法的基本描述。此算法的兩個輸入中,n是待檢測的數(shù),a是小于n的整數(shù)。如果算法的返回值為TRUE,則n肯定不是素數(shù);如果返回值為FALSE,則n有可能是素數(shù)。容易看出,在for循環(huán)結(jié)束時,d≡an-1modn,那么由費爾馬定理可知,如果n為素數(shù),則d為1;反之,若d≠1,則n不是素數(shù),返回TRUE。由于n-1≡-1modn,結(jié)合算法中變量x和d的聯(lián)系,可知for循環(huán)體內(nèi)的if條件(d=1)and(x≠1)and(x≠n-1)意味著方程x2≡1modn有非±1(模n)的解。因此,根據(jù)前述引理易知n不是素數(shù),算法返回TRUE。前述引理并不是充分必要條件,所以Miller-Rabin算法只是一種概率算法,如果該算法返回FALSE,則只能說n有可能是素數(shù)。為了用足夠大的概率確定n是素數(shù),通常對s個不同的整數(shù)a重復(fù)調(diào)用Miller-Rabin算法,只要其中有一次算法返回TRUE,則可以肯定n不是素數(shù);如果算法每次都返回FALSE,則以1-2-s的概率確信n就是素數(shù)。因此,當(dāng)s足夠大時,可以確定n就是素數(shù)。2.1.5中國剩余定理1.一次同余方程給定整數(shù)a,b,n,n>0,且n不能整除a,則ax≡bmodn稱為模n的一次同余方程,其中x為變量。顯然,如果一次同余方程ax≡bmodn有解x=x',則必然存在某個整數(shù)k,使得ax'=b+kn即ax'-kn=b因此,上面的一次同余方程有解的必要條件是d|b(其中d=gcd(a,n))另一方面,假如d=gcd(a,n)且d|b,那么由同余方程理論可知,滿足一次同余方程ax≡b(modn)的x與滿足同余方程

的x在取值上相同。因為

互素,存在,故方程有解,則所以方程ax≡bmodn也有解。這說明gcd(a,n)|b是一次同余方程ax≡bmodn有解的充分必要條件。定理2.3設(shè)整數(shù)a,b,n,n>0,且n不能整除a,令d=gcd(a,n),那么(1)如果d不能整除b,則一次同余方程ax≡bmodn無解。(2)如果d|b,則ax≡bmodn恰好存在d個模n不同余的解。證明

因為d|b是一次同余方程ax≡bmodn有解的充分必要條件,所以(1)是顯然的。下面證明(2)。當(dāng)d|b時,方程ax≡bmodn有解,設(shè)解為x0,則一定存在整數(shù)k0,使得那么對于任意整數(shù)t,構(gòu)造

則有

即axt≡bmodn,所以xt也是方程ax≡bmodn的解。由于t是任意的整數(shù),當(dāng)d|b時,一次同余方程ax≡bmodn有無窮個解。但由于

在模n下只有d個不相同的剩余類,且它們分別對應(yīng)t=0,1,…,d-1,所以一次同余方程ax≡bmodn只有d個模n不同余的解。此定理不僅告訴我們一次同余方程ax≡bmodn是否有解,而且還給出有解時的解數(shù)和求解方法。(1)利用歐幾里得算法求出d=gcd(a,n),若d不能整除b,則方程無解。(2)若d|b,則同余方程

有唯一解

只要利用擴展的歐幾里得算法求出

就能計算出這個解,并記為x0。(3)上面算出的x0

同樣也是同余方程ax≡bmodn的一個解,再令xt=x0+modn,并算出對應(yīng)t=0,1,…,d-1的值,即可得到同余方程ax≡bmodn的全部d個模n不同余的解。2.中國剩余定理我們解決了一次同余方程的求解問題,如果進(jìn)一步將若干個一次同余方程組成同余方程組,又該如何求解呢?這個問題是數(shù)論中的基本問題之一,我國古代數(shù)學(xué)家孫子給出了這個問題的答案,現(xiàn)在國際上一般稱這個問題為中國剩余定理,國內(nèi)稱為孫子定理。這個定理告訴我們,如果知道某個整數(shù)關(guān)于一些兩兩互素的模數(shù)的余數(shù),則可以重構(gòu)這個數(shù)。例如,如果已知x關(guān)于5和7的余數(shù)分別是2和3,即xmod5≡2且xmod7≡3,則在?35范圍內(nèi),x的唯一取值是17。同樣,?35中的每個數(shù)都可以用關(guān)于5和7的兩個余數(shù)來重構(gòu)。定理2.4(中國剩余定理)設(shè)n1,n2,…,nk是兩兩互素的正整數(shù),那么對任意的整數(shù)a1,a2,…,ak,一次同余方程組x≡aimodni(i=1,2,…,k)在同余意義下必有唯一解,且這個解是其中,即Ni-1

是Ni關(guān)于模數(shù)ni的逆(i=1,2,…,k)。證明

先證此同余方程組在同余意義下不會有多個解。若此同余方程組有兩個解c1

和c2,那么對所有ni(i=1,2,…,k)都有c1≡c2≡aimodni,故c1-c2≡0modni,ni|(c1-c2)。又因為所有的ni(i=1,2,…,k)兩兩互素,所以N|(c1-c2),即c1≡c2modN。因此,此同余方程組在同余意義下不可能有多個解。再證

就是此同余方程組的解。由于n1,n2,…,nk

兩兩互素,所以ni

與Ni

必然互素,因此Ni

關(guān)于模數(shù)ni

的逆Ni-1

存在。另一方面,NjNj-1≡1modnj,且若j≠i,則nj|Ni。因此所以N是此同余方程組的解。綜上,滿足定理條件的同余方程組有唯一解現(xiàn)在來看我國古代《孫子算經(jīng)》上的一個問題:“今有物,不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問物幾何?”這個問題實際上就是求同余方程組的正整數(shù)解。書中給出滿足這一問題的最小正整數(shù)解是x=23,所用的解法就是中國剩余定理。因此,國際上所說的中國剩余定理也稱為孫子剩余定理或?qū)O子定理。實際上,所有模N=3×5×7=105同余23的正整數(shù)都是上面問題的解。2.1.6模為素數(shù)的二次剩余二次剩余是數(shù)論中一個非常重要的概念,許多數(shù)論問題都要用到二次剩余理論,這一小節(jié)我們來了解一下模為素數(shù)的二次剩余。對于一般形式的二次同余方程ax2+bx+c≡0modp通過同解變形和變量代換,可化為這里y≡(2ax+b)modp,d≡(b2-4ac)modp,p為素數(shù),a是與p互素的整數(shù)。當(dāng)p|d時,二次同余方程(21)僅有解y≡0modp,所以下面一直假定p與d互素。另外,如果素數(shù)p=2,則僅可取d≡1mod2,這時方程(21)僅有解y≡1modp,故以下定義恒假定p為大于2的素數(shù),即奇素數(shù)。設(shè)p是奇素數(shù),d是與p互素的整數(shù),如果方程x2≡dmodp有解,則稱d是模p的二次剩余或平方剩余,否則稱d是模p的二次非剩余。定理2.5(Euler準(zhǔn)則)設(shè)p是奇素數(shù),d是與p互素的整數(shù),那么d是模p二次剩余的充要條件是d(p-1)/2≡1modpd是模p非二次剩余的充要條件是d(p-1)/2≡-1modp證明

先證對于任何與p互素的d,d(p-1)/2≡1modp與d(p-1)/2≡-1modp有且僅有一式成立。由于d與p互素,由歐拉定理或費爾馬定理可知d(p-1)≡1modp因此,有即由于p是奇素數(shù),即p>2,且所以有且僅有一式成立,即

有且僅有一式成立,所以

有且僅有一式成立。下面證明d是模p的二次剩余的充要條件是同余式

成立。先證必要性。若d是模p的二次剩余,則必定存在x0,使得因而有由于d與p互素,所以x0

也與p互素,由歐拉定理可知所以必要性得證。

再證充分性。設(shè)成立,那么d與p必定互素?？疾橐淮瓮喾匠塘頺取遍?n={1,2,…,p-1}中的每一個整數(shù),則有k與p互素,且對每一個k上面的同余方程存在唯一的解x∈?n。如果d不是模p的二次剩余,則每一個k與對應(yīng)的解x不相等。這樣,?n

中的p-1個數(shù)可以按k與x配對,且兩兩配完,共(p-1)/2對。因此有

由數(shù)論中的結(jié)論

得這個結(jié)果與前提

條

件

矛

盾,所

以

假

設(shè)d不

是

模p的

二

次

剩

余

是

錯

誤

的,即

如果那么d必是模p的二次剩余。充分性得證。由上面兩部分的證明,可以推出Euler準(zhǔn)則的剩余部分。由Euler準(zhǔn)則容易得出下面兩個推論。推論1-1是模p的二次剩余,當(dāng)且僅當(dāng)p≡1mod4,這里p是奇素數(shù)。推論2設(shè)p是奇素數(shù),d1,d2

均與p互素,那么(1)若d1,d2均為模p的二次剩余,則d1,d2也是模p的二次剩余。(2)若d1,d2均為模p的非二次剩余,則d1,d2

是模p的二次剩余。(3)若d1

是模p的二次剩余,d2

是模p的非二次剩余,則d1,d2

是模p的非二次剩余。Euler準(zhǔn)則告訴我們?nèi)绾闻卸ㄒ粋€整數(shù)d是否模p的二次剩余(p是奇素數(shù)),但對于一個模p的二次剩余d,如何求出d的兩個平方根?求解這個問題沒有簡練的方法,這里我們給出一類特殊模數(shù)的平方根的求法。

定理2.6若p≡3mod4,d是模p的二次剩余,那么d模p的兩個平方根是證明

由于d是模p的二次剩余,由歐拉準(zhǔn)則可知所以,有因此

是d模p的兩個平方根。2.1.7?p

上的離散對數(shù)

設(shè)計公鑰密碼算法的關(guān)鍵是尋找一個符合密碼學(xué)要求的陷門單向函數(shù),構(gòu)造這樣的陷門單向函數(shù)的思路主要有兩種:一種思路是以RSA算法為代表的一類算法所使用的以大整數(shù)分解為基礎(chǔ)的構(gòu)造方法,另一種思路是利用離散對數(shù)來構(gòu)造陷門單向函數(shù)。那么什么是離散對數(shù)呢?這里我們介紹一種最簡單的離散對數(shù),即建立在?p上的離散對數(shù)。認(rèn)識離散對數(shù)要從模指數(shù)運算開始,模指數(shù)函數(shù)為其中,a,x,y和p都是正整數(shù),且在密碼學(xué)里總是要求p為素數(shù)。顯然,在模指數(shù)函數(shù)中,如果已知a,x和p,則很容易計算出函數(shù)值y?，F(xiàn)在反過來看問題,如果已知y,a和p,能否求出x呢?或者說,能否找到x,使之滿足ax≡ymodp。這實際上就是模指數(shù)函數(shù)的反函數(shù),也就是我們所說的離散對數(shù),并且可將其表示成

由于這里要求a,x,y和p都是正整數(shù),因此不是所有的離散對數(shù)都有解。例如,很容易驗證方程3x≡7mod13無解。也就是說離散對數(shù)y≡log73mod13是無解的(在整數(shù)范圍內(nèi))?，F(xiàn)在,在?p

上考查模指數(shù)函數(shù)y≡axmodp,令y=1,則可得一個模指數(shù)方程ax≡1modp由歐拉定理可知,如果a∈?p,則有a與p互素,那么上面的模指數(shù)方程至少有一個解(比如x=φ(p))。在數(shù)論中將滿足上述方程的最小正整數(shù)x稱為a模p的階。a模p的階一定是φ(p)的因子。這是因為,假如a模p的階(記為m)不是φ(p)的因子,則φ(p)可表示成φ(p)=km+r(其中0<r<m)那么即這與m是a模p的階矛盾。如果a模p的階等于φ(p),則稱a是p的本原根。由于φ(p)=p-1,所以當(dāng)a是p的本原根時,有a1,a2,…,ap-1在同余意義下互不相同,且都與p互素。也就是說,當(dāng)x∈?p*={1,2,…,p-1}時,模指數(shù)函數(shù)y≡axmodp是?p*

到?p*的一一映射。下面給出離散對數(shù)的嚴(yán)格定義。

設(shè)p是素數(shù),正整數(shù)a是p的本原根,那么對?y∈{1,2,…,p-1},必定存在唯一的x∈{1,2,…,p-1},使得y=axmodp。此時稱x為模p下以a為底y的離散對數(shù),記為x≡logaymodp,但習(xí)慣上仍然寫成y≡logaxmodp。離散對數(shù)有如下性質(zhì):性質(zhì)1loga1≡0modp。性質(zhì)2logaa≡1modp。性質(zhì)3logaxymodp≡(logaxmodp+logaymodp)modφ(p)。上述性質(zhì)1和性質(zhì)2可以由關(guān)系式a0≡1modp,a1≡amodp直接得出。性質(zhì)3的證明需要用到如下引理。引理2.2設(shè)a與p為互素的正整數(shù),如果am≡anmodp,則有m≡nmodφ(p)。因為a與p互素,所以a存在模p的逆元a-1。同余

式am≡anmodp兩

邊

同

乘(a-1)n,得到又由歐拉定理知所以一定存在整數(shù)k,使得即現(xiàn)在證明性質(zhì)3。證明

由離散對數(shù)的定義可知:所以由模運算的性質(zhì)可得根據(jù)前面的引理,有性質(zhì)3:前面已經(jīng)提到,如果已知a,x和p,那么使用快速指數(shù)算法可以很容易地計算出函數(shù)y≡axmodp,但如果已知a,y和p,能不能輕易地計算出離散對數(shù)x≡logaymodp呢?現(xiàn)

在

的

回

答

是

很

困

難,目

前

已

知

的

求

離

散

對

數(shù)

問

題

的

最

好

算

法

的

時

間

復(fù)

雜

度

為

因此,當(dāng)p很大時,計算離散對數(shù)在時間上是不可行的,也正是這個原因使離散對數(shù)可以用于設(shè)計單向陷門函數(shù)。2.2計算復(fù)雜性問題OdedGoldreich在他的著作FoundationsofCryptography:BasicTools提到了定義“安全”的兩種途徑:基于信息論的經(jīng)典方法和基于計算復(fù)雜性的現(xiàn)代方法。利用信息論考查安全,主要手段是度量密文中包含明文的信息量;而采用計算復(fù)雜性討論安全,則是給出破解密文的難度,即是否能有效獲取明文的完整信息。某些問題,如公鑰加密體制,是不能用傳統(tǒng)的信息論方法來研究的。隨著計算復(fù)雜性和密碼學(xué)研究的相互融合,計算復(fù)雜性方法成為研究密碼學(xué)所必須掌握的工具。本章簡要介紹確定型圖靈機、非確定型圖靈機、概率圖靈機這3個基本計算模型,在此基礎(chǔ)上討論非確定性多項式時間完全問題和加密體制是否安全之間的關(guān)系,以及多項式時間不可區(qū)分性。2.2.1確定性多項式時間1.算法效率分析

算法(Algorithm)就是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。前面已經(jīng)介紹了幾種算法,但未對其做詳細(xì)的效率分析。本節(jié)主要給出衡量算法效率的方法,它是后續(xù)幾節(jié)的基礎(chǔ)。一般而言,分析某算法的效率存在如下兩個指標(biāo):(1)時間復(fù)雜度(TimeComplexity):該算法完全運行所需運算時間的多少。(2)空間復(fù)雜度(SpaceComplexity):該算法完全運行所需存儲空間的大小。

在理論和實際中,由于使用者更關(guān)心問題解決的快慢,所以時間復(fù)雜度更為重要。隨著技術(shù)的發(fā)展,存儲設(shè)備的價格不斷下降,對空間復(fù)雜度的關(guān)注越來越少。衡量時間復(fù)雜度最精確也最原始的辦法是在某臺計算機上執(zhí)行算法,經(jīng)過測量后得到關(guān)于它的評價。但這種時間復(fù)雜度的測試與具體機器有關(guān),不同的計算機有不同的性能和結(jié)構(gòu),測量值自然不同。即便在同一臺計算機上,算法的每次執(zhí)行時間也會有一些偏差。為此,對時間復(fù)雜度的漸進(jìn)分析是必要的。插入排序效率分析如下://這段程序?qū)nt型數(shù)組a進(jìn)行插入排序,數(shù)組長度為n

顯然,每一次循環(huán)的程序步數(shù)最少是4,最多是2i+4。整個程序在最好情況下需要執(zhí)行4n次,在最壞情況下需要執(zhí)行

次。計算出其上下界可了解該算法的執(zhí)行時間。

假定該算法執(zhí)行5次插入操作,并且假設(shè)這5次操作的實際程序步數(shù)分別為4,4,6,10,8,那么該操作序列的實際程序步數(shù)為4+4+6+10+8=32。該指標(biāo)和上下界有一定的差距,而復(fù)雜的算法,其時間復(fù)雜度變化可能相當(dāng)大。為描述由于輸入數(shù)據(jù)而導(dǎo)致的時間復(fù)雜度差異,可用平均時間復(fù)雜度描述,即設(shè)算法執(zhí)行i步出現(xiàn)的概率為pi,則平均時間復(fù)雜度為

與此對應(yīng),漸近時間復(fù)雜度存在最好情況、最壞情況和平均情況3種度量指標(biāo)。最壞情況下的時間復(fù)雜度漸進(jìn)分析由Hopcroft和Tarjan最先提出,其目的是給算法分析一個不依賴具體硬件的定量方法。假定f(n)、g(n)均為非負(fù)函數(shù),定義域均為?。問題的輸入規(guī)模為n,為描述漸進(jìn)復(fù)雜度中的階,定義如下漸進(jìn)記號(AsymptoticNotation):O:當(dāng)且僅當(dāng)?c,n0,?n(n≥n0→f(n)≤c×g(n)),稱f(n)=O(g(n))。Ω:當(dāng)且僅當(dāng)?c,n0,?n(n≥n0→f(n)≥c×g(n)),稱f(n)=Ω(g(n))。Θ:當(dāng)且僅當(dāng)f(n)=O(g(n))與f(n)=Ω(g(n)),稱f(n)=Θ(g(n))。我們通常分析的是時間的漸進(jìn)復(fù)雜度,需要估計出t(n)=O(tasymptotic(n))。O記號經(jīng)常被采用(PaulBachmann于1894年引入),因為它指出了算法時間的上界,也較好估算。更為精確的Θ記號大多時候較難計算,較少采用。此外,O記號僅表示函數(shù)的上界,它不意味著最壞情況,各種情況下均有此記號。

一般而言,各種階的增長速度不同,輸入規(guī)模增大時,增長速度慢的階可認(rèn)為是快速算法。常用的階按照增長速度遞增排序為O(c)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2n)<O(n!)<O(nn)

其中,O(c)一般寫為O(1),它是理論上的最佳算法;O(n)稱為線性算法,它是實際中常見的最好算法;而O(nn)是最差算法,相當(dāng)于窮舉搜索。

多項式算法是有效算法,即時間復(fù)雜度為O(nk)(k∈?)的算法是有效算法。2.問題的難度

對于某個問題而言,需要對其難度進(jìn)行描述。一個自然的想法是:該問題若存在有效算法,則認(rèn)為它是較簡單的問題,反之則認(rèn)為它是較困難的問題。1)排序問題的難度

元素的

排

序

問

題

可

用

堆

排

序(HeapSort)解

決,最

壞

情

況

下

的

時

間

復(fù)

雜

度

為O(nlogn)。注意到O(nlogn)也是O(n2),可知堆排序算法是有效算法,進(jìn)而可認(rèn)為排序問題是較簡單的問題。事實上,基于比較方法的排序算法時間下界是Ω(nlogn),堆排序也是解決排序問題的最好算法之一。

為引入更一般的定義,下面介紹圖靈機(TuringMachine,TM)的概念,引入它的主要目的是形式化給出“計算”(Computation)的模型。當(dāng)然,計算模型不只TM一種,λ演算、遞歸函數(shù)等都是計算模型,它們相互等價。計算理論領(lǐng)域?qū)Υ擞幸粋€被普遍接受的論題,即著名的Church-Turing論題。TheChurch-TuringThesis(丘奇-圖靈論題)在直觀上可計算的函數(shù)類就是TM(以及任意與TM等價的計算模型)可計算的函數(shù)類。

討論計算模型時,首先對計算進(jìn)行抽象。A.M.Turing仔細(xì)研究了人類計算的過程,他把人類的計算抽象成計算者、筆、紙3個基本要素。Turing認(rèn)為只要存在這3個要素,即可模擬計算的全過程。假定存在某個旁觀者,他不認(rèn)識計算者所采用的符號,以他所看到的過程作為模擬,旁觀者認(rèn)為計算者一直在進(jìn)行兩種類型的操作:在紙上書寫某些符號和把筆移動到紙上某位置。計算者采用的符號類型是有限的,他每次書寫的符號可由紙上現(xiàn)有符號和他自身的狀態(tài)決定。事實上,旁觀者觀察到的過程即是抽象化的計算過程。為方便以后的討論,Turing進(jìn)一步把紙簡化成一條無限長的紙帶,該紙帶由無限方格組成。計算者每次只能移動紙帶或者改變某方格內(nèi)的符號,并且他每一時刻只能處于某一特定狀態(tài),狀態(tài)的變化就是計算者行為的抽象。

上面給出的

這

種

簡

單

的TM是

確

定

性

的,即

確

定

型

圖

靈

機(DeterministicTuringMachine,DTM)。DTM在給定輸入數(shù)據(jù)后,其后它每一步的動作都可完全確定。每一時刻的DTM可用格局(Configuration)來描述,它包括紙帶的內(nèi)容、讀寫頭的位置和控制器的狀態(tài)。一臺DTM由如下要素組成,如圖2-1所示。(1)符號表Σ:由有限個符號組成,包括標(biāo)識空白的特殊字符*。(2)可雙向移動的無限長紙帶:由無限個方格組成,方格上的符號均屬于Σ,除了有限個方格外,其他方格上的符號均為*。(3)讀寫頭:可在任一時刻對某個確定的方格進(jìn)行操作。此讀寫頭可向左(←)或向右(→)移動。(4)控制器:攜帶狀態(tài)集Γ,包括特定的起始狀態(tài)γ0和停機狀態(tài)集?。DTM的計算可由轉(zhuǎn)移函數(shù)(TransitionFunction)決定:δ:Γ×Σ→?！力病羬←,→}

若控制器當(dāng)前狀態(tài)為γn

且讀寫頭指向方格內(nèi)容為σn,轉(zhuǎn)移函數(shù)δ(γn,σn)可完成如下工作:(1)若γn∈?,則計算停止(也稱停機),否則確定控制器的下一步狀態(tài)γn+1。(2)修改讀寫頭指向方格內(nèi)容,將其改為σn+1。(3)確定讀寫頭移動的方向,要么向左(←),要么向右(→)。

確定型圖靈機模型易于理解:輸入固定的程序和數(shù)據(jù)(此處隱含了馮·諾依曼結(jié)構(gòu)中不區(qū)分程序和數(shù)據(jù)的思想),然后DTM按照輸入完全確定性地運行。不過DTM的構(gòu)造相當(dāng)復(fù)雜,在實際

中

往

往

采

用

更

接

近

現(xiàn)

實

計

算

機

的

模

型,如RASP、RAM等,它

們

均

與DTM等效,此處不再贅述。

一般而言,DTM如果停機,運行結(jié)果只能是兩種:接受或不接受。于是停機狀態(tài)集?

可劃分為接受狀態(tài)集?Y={γT}與不接受狀態(tài)集?N={γF}。接受格局(AcceptingConfiguration)意味著DTM停機時,控制器狀態(tài)屬于?Y,DTM不接受該輸入就是控制器狀態(tài)屬于?N。于是DTM可等價于一臺能回答問題的機器,接受輸入數(shù)據(jù)計算后僅可回答Yes或No。至于DTM是否停機屬于可計算性(Computability)領(lǐng)域所研究的問題,可參閱相關(guān)書籍。

表面上,DTM只能以停機來表示接受輸入的程序和數(shù)據(jù),它是如何和日常使用的計算機等價呢?這需要引入判定問題(DecisionProblem)。判定問題就是指問題的答案僅有Yes或No。最優(yōu)化問題均可轉(zhuǎn)化為對應(yīng)的判定問題,若該問題存在有效算法,當(dāng)且僅當(dāng)其對應(yīng)的判定問題存在有效算法。2)最短路徑問題的判定問題

最短路徑問題的判定問題僅考慮路徑長度均為非負(fù)整數(shù)的情況。定義判定問題為“是否存在長度小于等于L的路徑?”容易計算出路徑長度的上界M,于是可對L從0開始遞增到M,給出一系列判定問題。解決每個判定問題,直到找到某個回答為Yes的L,該值即為所求最短路徑。利用此判定問題可解決最短路徑問題。

對于一般的問題,可先將該問題轉(zhuǎn)換成判定問題,然后利用DTM回答的答案解決。密碼學(xué)中大量涉及的是離散優(yōu)化問題,它們均可以轉(zhuǎn)換成相應(yīng)的判定問題,本章中的問題大部分為判定問題。一個粗略的結(jié)

論

是:DTM的

計

算

能

力

與

日

常

使

用

的

計

算

機

等

效。DTM的輸入成為語言，了解DTM的定義后，可給出較簡單的問題的定義，即P的確定型的圖靈機上的具有有效算法的判定的集合。

DTM是有效算法的模型表示,即任何確定性有效算法均可由DTM實現(xiàn),且可以在多項式時間內(nèi)運行,這就是多項式時間Church-Turing論題(thePolynomial-TimeChurch-TuringThesis)。

通過對DTM的討論,可知DTM代表了計算的能力,于是問題的難度即可定義為:某問題存在有效算法則稱之為易解的(Tractable);如果不存在多項式算法則稱之為難解的(Intractable)。該定義等價于:L是易解的,當(dāng)且僅當(dāng)L∈P。這就是著名的Cook-Karp論題。2.2.2非確定性多項式時間

如果所有的問題都存在有效算法,那么密碼就沒有存在的價值,因為破譯密碼可以通過有效算法輕易解決。事實上,大多數(shù)問題目前還未發(fā)現(xiàn)有效算法。這些未解決的問題中有一個巨大的問題子集,它們擁有共同的特點,即對于這些問題的正確答案能在多項式時間內(nèi)驗證。一個最簡單的例子就是判定某數(shù)是否合數(shù),如果有人聲稱找到了其約數(shù),就可以在多項式時間內(nèi)驗證。計算機科學(xué)和密碼學(xué)中可找到許多類似的問題,它們的集合稱為NP。

當(dāng)然也有大量問題是超出NP的。輸出全排列就是一個超出NP的典型例子,該問題屬于P-Space(PolynomialSpace)。

容易驗證P是NP的子集,但P是否NP的真子集呢?此問題被稱為P=NP?問題,它是計算復(fù)雜性領(lǐng)域,甚至整個計算機科學(xué)理論的焦點問題。(注意:了解P的定義后,常有人認(rèn)

為NP是Non-Polynomial的

縮

寫。事

實

上,這

里

的“N”是“非

確

定

性”(Non-Deteministic)的縮寫。如果NP是Non-Polynomial,有關(guān)P=NP?的討論也將不復(fù)存在。)可滿足性問題(BooleanSatisfiability)為:給定某布爾表達(dá)式,是否存在某一組對其變量的真假賦值,使得該布爾表達(dá)式為真。此問題可在多項式內(nèi)驗證,所以它是NP問題。例如,S=((p1∨p2)∧p3),需判斷p1,p2,p3

在何種賦值下,可使S為真。當(dāng)p1,p2,p3

在1,0,1情況下,可知S為真,易知該驗證算法為有效算法。目前給出的解決可滿足性問題的算法均為指數(shù)算法,其上界為O(2n)。這些算法的基本思路均為回溯(BackTracking)。最簡單的蠻力算法如圖22所示。該算法從根結(jié)點開始搜索,分別給p1,p2,p3

賦值為0或1,搜索每個可能的結(jié)點(可剪去某些不可能的子樹),最終得到是否可滿足。為介紹NP,下面簡要描述關(guān)于非確定型圖靈機(Non-deterministicTuringMachine,NTM)的概念,這里不給出其精確定義,僅給出它的兩種直觀解釋。(1)NTM會自動選擇最優(yōu)路徑進(jìn)行計算。在上面的可滿足性問題中,可假定NTM擁有一個具有預(yù)測能力的神奇硬幣,根據(jù)它拋擲后的結(jié)果進(jìn)行選擇:若是正面,則提示下一步該選擇1;若是反面,則選擇0。NTM在進(jìn)行計算的時候,最優(yōu)路徑會提示給p1,p2,p3

賦值1,0,1。這樣可利用此解答驗證其可滿足性。(2)NTM在進(jìn)行計算時,碰到需要選擇的分支,則對自身進(jìn)行復(fù)制,每個分支分配一個副本進(jìn)行計算,這樣只需要多項式時間即可判定其可滿足性。顯然,NTM的計算能力極強,遠(yuǎn)遠(yuǎn)超出目前計算機的能力。它不可能對應(yīng)通常意義上的算法,更不可能在目前的實際計算中實現(xiàn)。NP是非確定型圖靈機上的存在有效算法的判定問題的集合。從NP的定義可看出,NP問題的本質(zhì)不是多項式時間內(nèi)可驗證,而是在NTM上可找到有效算法。這意味著如果有相當(dāng)“智能”的信息引導(dǎo),有望對其獲得突破,即能在DTM上找到有效算法,這是多數(shù)組合優(yōu)化問題均不可回避的難點。如果不用NTM進(jìn)行描述,還可以僅從判定問題的角度來認(rèn)識NP。這樣,P問題是指能夠在多項式時間求解的判定問題,而NP問題則是指那些“肯定解”(回答為是)能夠在給定的正確信息下在多項式時間內(nèi)驗證的判定問題。對于可滿足性問題,目前僅能找到指數(shù)級的算法,一個很自然的問題就是,它存在有效算法嗎?目前的回答是不確定。除此之外,還有一大批NP問題,目前既找不到有效算法,又不能確定它不存在有效算法。這類問題具有非常特殊的性質(zhì),即如果其中一個存在有效算法,那么此類問題均存在有效算法,這類問題統(tǒng)稱為NP完全(NP-Complete,NPC)問題。Cook于1971年給出了第一個NPC問題,即可滿足性問題。此后,大量NPC問題被發(fā)現(xiàn),對它們的研究集中在尋找有效算法上,如果在其中一個問題上取得突破,那么NPC問題全部存在有效算法,并可確定P=NP。不過,大多數(shù)學(xué)者認(rèn)為NPC問題不存在有效算法,也即假定NPC問題是難解的。圖2-3給出了在此假設(shè)下NP中各類問題的關(guān)系。密碼學(xué)家根據(jù)NPC問題是難解的假設(shè),設(shè)計了相當(dāng)多的加密體制。這些體制主要利用單向函數(shù)(OneWayFunction)的思想,原理是該類函數(shù)正向計算存在有效算法,其反向計算是難解問題。一般而言,基于NPC問題設(shè)計的加密體制比較安全。值得注意的是,某些基于NPC問題設(shè)計的加密體制不甚安全,也已經(jīng)被攻破。Merkle-Hellman加密體制(Cryptosystem)是最早提出的公鑰密碼體制,其本質(zhì)是背包加密算法。該方法基于子集和問題(SubsetSumProblem),即對于一個由正整數(shù)組成的集合和某個給定的數(shù)Sum,是否存在該集合的某個子集,其元素之和恰好等于Sum。子集和問題是NPC問題,從表面上看該體制很安全。1982年,Shamir利用Lenstra-Lenstra_x0002_Lovász(L3)格基約簡(LatticeBasisReduction)算法破解了Merkle-Hellman加密體制。不過Merkle-Hellman加密體制的加密和解密速度很快,盡管它已被破解,但依然有其價值。需要指出,此問題的解決不等于NPC問題存在有效算法。此外,有些加密算法所采用的NP問題雖然未被肯定是NPC問題,但在實踐上得到了良好的應(yīng)用。RSA算法即是一個典型的例子,目前對其尚無有效算法。2.2.3概率多項式時間NPC問題目前雖然尚無有效算法,但該類問題在實際應(yīng)用中經(jīng)常出現(xiàn),于是提出了兩類算法來部分解決此類問題:概率算法(ProbabilisticAlgorithm)(也稱隨機算法(RandomizedAlgorithm))與近似算法(ApproximationAlgorithm)。密碼學(xué)中經(jīng)常用到概率算法,如何判定其優(yōu)劣是本節(jié)所討論的問題。NTM從本質(zhì)上可認(rèn)為是從不犯錯的機器,它總能找到正確的路徑。而人在預(yù)測中總會犯一定的錯誤,不同的人犯錯誤的可能性不同。一般來說,經(jīng)驗豐富的人犯的錯誤少,沒有經(jīng)驗的人犯的錯誤多,這種現(xiàn)象可用他們犯錯誤的概率定量描述。概率圖靈機(ProbabilisticTuringMachine,PTM)是一臺總停機的NTM,它在每個格局中至多有兩個格局,從當(dāng)前格局等可能地到達(dá)其中之一。PTM停機的狀態(tài)有3種:接受、不接受和未知。如果PTM停機在未知狀態(tài),稱該計算無效。如果PTM是多項式界限且沒有未知狀態(tài),稱該機為