演算法93试除因数分解法的虚拟码范例930课件.ppt

1、9.3 因數分解因數分解因數分解（factorization）的問題從過去一直被研究至今，而這樣的研究在未來似乎會持續下去。因數分解在公開金鑰密碼系統（參見第十章）的安全性扮演一個非常重要的角色。本節討論主題算術的基本定理因數分解的方法費瑪分解法Pollard p 1分解法Pollard rho分解法更快速的分解法9.3.1 算術的基本定理算術的基本定理最大公因數 最小公倍數 演算法演算法 9.3 試除因數分解法的虛擬試除因數分解法的虛擬碼碼範例範例9.30使用試除因數法來找出 1523357784 的因數。解法：我們執行一個程式並得到以下的結果。9.3.3 費瑪分解法費瑪分解法費瑪因數分解法

2、（Fermat factorization method，演算法 9.4）可以將一個數值 n 分解成 兩個正整數 a 和 b（不一定為質數），使得 n=a b。演算法演算法 9.4 費瑪因數分解法的虛擬費瑪因數分解法的虛擬碼碼9.3.4 Pollard p 1 分解法分解法此方法植基於一個條 件：p 1 不能有大於預定邊界 B 的因數。Pollard 證明在這種條件之下：演算法演算法 9.5 Pollard p 1 因數分因數分解法的虛擬碼解法的虛擬碼範例範例9.31使用 Pollard p 1 分解法來求出 57247159 的因數，其中邊界 B=8。解法：我們依這個演算法執行程式，並找出

3、p=421。事實上，57247159=421 135979。注意421 是質數，而且 p 1 沒有任何大於 8 的因數（421 1=22 3 5 7）。圖圖 9.3 Pollard rho 的連續數值的連續數值演算法演算法 9.6 Pollard rho 分解法的分解法的虛擬碼虛擬碼範例範例9.32假設有一台電腦 1 秒可以執行 230（將近 10 億）次位元運算，其分解下列大小的整數 大約需要多少時間？a.60 位數。b.100 位數。範例範例9.32(續續)解法：a.一個 60 位數將近有 200 個位元，其複雜度為 2nb/4 或 250。當每秒可以執行 230 次運算時，此演算法可以在

4、 220 秒完成，大約為 12 天。b.一個 100 位數將近有 300 個位元，其複雜度為 275。當每秒可以執行 230 次運算時，此演算法可以在 245 秒完成，需要好幾年。範例範例9.33我們寫出一個程式來分解 434617，其結果為 709（434617=709 613）。表 9.2 顯 示執行此程式時的數對（x 和 y）以及 p 的值。表 9.2 9.3.6 更快速的分解法更快速的分解法二次篩選法這個方法 使用篩選方式來找出 x2 mod n 的值。數體篩選法這個方法在代數的環結構中使用篩選方式來找出 x2 y2 mod n。O(eC),其中其中 C (ln n lnln n)1/

5、2O(eC),其中其中 C 2(ln n)1/3(lnln n)2/3範例範例9.34假設有一台電腦 1 秒可以執行 230（將近 10 億）次位元運算。使用下列方法來分解一 個 100 位數的整數，大約各需要多少時間？a.二次篩選法。b.數體篩選法。解法：一個 100 位數將近有 300 個位元（n=2300）。ln(2300)=207，而 lnln(2300)=5。a.(207)1/2 (5)1/2=14 2.23 32 e32 (e32)/(230)20 小時b.(207)1/3(5)2/2=6 3 18.e18 (e18)/(230)6 秒9.4 中國餘數定理中國餘數定理中國餘數定理（

6、Chinese remainder theorem,CRT）是用來求解模數兩兩相異且互質之單變數的同餘方程組。此方程組如下所述：範例範例9.35以下範例為模數均相異的同餘方程組：我們將在下一節說明這個方程組的解法；目前，先注意到這個方程組的解為 x=23。這個值可以滿 足所有的方程式：23 2(mod 3)、23 3(mod 5)和 23 2(mod 7)。範例範例9.35(續續)解法：我們可以依照以下的步驟來解這個方程組：求出 M=m1 m2 mk。這是所有方程式共同的模數。求出 M1=M/m1,M2=M/m2,Mk=M/mk。在相對應的模數(m1,m2,mk)下，求出 M1,M2,Mk的乘

7、法反元素 M11,M21,Mk 1。這些方程式共同的解為：範例範例9.38假設我們需要計算 z=x+y，其中 x=123 和 y=334，但系統只允許使用小於 100 的 數值。這些數值可以用下列表示法來代替：範例範例9.38(續續)將每一組模數相同的 x 和 y 相加，我們得到 P.257 現在，我們可以用中國餘數定理來解這三個方程式，並求出 z，其中一個可以滿足這些方程式 的解為 z=457。9.5 二次同餘二次同餘在密碼學中，我們也必須探討二次同餘（quadratic congruence），亦即形式為 a2x2+a1x+a0 0(mod n)的方程式。此處我們將探討的範圍限制在 a2=

8、1 和 a1=0 的二次方程式，亦即形式為x2 a(mod n)的方程式。9.5 二次同餘二次同餘(續續)本節討論主題模數為質數的二次同餘模數為合成數的二次同餘範例範例9.39方程式 x2 3(mod 11)有兩個解，x 5(mod 11)和 x 5(mod 11)。但我們注意到5 6(mod 11)，所以此方程式真正的解為 5 和 6，同時這兩個解是非同餘的。二次剩餘與非二次剩餘二次剩餘與非二次剩餘在方程式 x2 a(mod p)中，如果此方程式有兩個解，a稱為二次剩餘；如果此方程式無解，a 稱為非二次剩餘。範例範例9.41在 Z11*中有十個元素，其中剛好有五個是二次剩餘，而另五個是非二次

9、剩餘。換句話說，我們可以將 Z11*分成兩個不同的集合：QR 和 QNR，如圖 9.4 所示。尤拉準則尤拉準則若 a(p 1)/2 1(mod p)，則 a 在模 p 下是二次剩餘。若 a(p )/2 1(mod p)，則 a 在模 p 下是非二次剩餘。範例範例9.42為了確認 14 或 16 在 Z23*是否為 QR，我們計算：解出模數為質數的二次方程式解出模數為質數的二次方程式特殊形式：p=4k+3 範例範例9.43求解下列各二次方程式：a.x2 3(mod 23)b.x2 2(mod 11)c.x2 7(mod 19)範例範例9.43(續續)解法：a.在第一個方程式，3 在 Z23 中是

10、 QR。解為 x 16(mod 23)。亦即，b.在第二個方程式，2 在 Z11 中是 QNR。在 Z11 中無解。c.在第三個方程式，7 在 Z19 中是 QR。解為 x 11(mod 19)。亦即，圖圖 9.5 模數為合成數之二次同餘方模數為合成數之二次同餘方程式的解法程式的解法複雜度複雜度求解一個模數為合成數之二次同餘式的難度有多高？其主要難度在於模數的因數分解。換句話說，求解一個模數為合成數之二次同餘式的難度，等同於對一個合成數進行因數分解。如之前所述，當 n 很大時，因數分解是不可行的。求解一個模數為合成數的二次同餘式的難度，等同於對該模數進行因數分解。注意注意9.6 指數運算與對數

11、運算指數運算與對數運算 本節討論主題指數運算對數運算快速指數運算快速指數運算我們可以使用平方暨乘演算法(square-and-multiply method)來進行快速的指數運算。圖9.6 演算法演算法 9.7 平方暨乘演算法的虛擬平方暨乘演算法的虛擬碼碼範例範例9.45圖 9.7 顯示利用演算法 9.7 來計算 y=ax 的流程（為了簡化，圖中省略模數）。在這個範例中，x=22=(10110)2。其指數有五個位元。圖 9.7表表9.3 計算計算 1722 mod 21複雜度複雜度快速指數運算演算法的位元複雜度是以多項式成長。注意注意演算法演算法 9.8 模對數運算的暴力搜尋模對數運算的暴力搜

12、尋法法範例範例9.46群 G=的秩為何？|G|=(21)=(3)(7)=2 6=12。在此群中有 12 個元素：1、2、4、5、8、10、11、13、16、17、19 和 20。這些元素都與 21 互質。範例範例9.47求出在群 G=中所有元素的秩。解法：這個群只有(10)=4 個元素：1、3、7、9。我們可以使用嘗試錯誤法來找出每一個元素的秩。11 1 mod(10)ord(1)=131 3 mod(10)；32 9 mod(10)；34 1 mod(10)ord(3)=4 71 7 mod(10)；72 9 mod(10)；74 1 mod(10)ord(7)=4 91 9 mod(10)

13、；92 1 mod(10)ord(9)=2 範例範例9.48表 9.4 顯示對於群 G=，ai x(mod 8)的結果。注意，(8)=4。其元素為1、3、5 和 7。表 9.4原根原根在群 G=中，當一個元素的秩和(n)相等時，則該元素稱為群 G 的原根。只有當 n=2,4,pt 或 2pt 時，群 G=才會有原根。注意注意若群 G=有原根，則其原根的個數為(n)。範例範例9.49表 9.4 顯示出群 G=沒有原根。因為沒有任何元素的秩等於(8)=4。所有元素的秩都小於 4。範例範例9.50表 9.5 顯示對於群 G=，ai x(mod 7)的結果。在這個群中，(7)=6。表 9.5 範例範例

14、9.51當 n 等於下列哪些值時，群 G=會有原根：17、20、38 和 50？解法G=有原根，因為 17 是質數（p t，其中 t 等於 1）。G=沒有原根。G=有原根，因為 38=2 19，而 19 是質數。G=有原根，因為 50=2 52，而 5 是質數。循環群循環群若 g 是群中的一 個原根，我們可以產生集合 Zn*如下：範例範例9.52群 G=有兩個原根，因為(10)=4 和(10)=2。我們可以找到其原根為3 和 7。以下顯示我們如何使用每一個原根來產生整個集合 Z10*。離散對數的概念離散對數的概念群 G=具有一些有趣的性質：它的元素包含了從 1 到 p 1 的所有整數。它一定有原根。它是可循環的。我們可以使用 gx 來產生群中所有的元素，其中 x 是從 1 到(n)=p 1 中的一個整數。我們可以把原根視為對數運算的底數。離散對數問題與因數分解問題的複雜度是相同的。表表 9.6 G=的離散對數的離散對數範例範例9.53求出下列各式的 x 值：a.4 3x (mod 7)b.6 5x (mod 7)解法：使用表 9.6 可以很容易地找出答案。a.4 3x mod 7 x=L34 mod 7=4 mod 7b.6 5x mod 7 x=L56 mod 7=3 mod 7表表 9.7 傳統對數與離散對數的比較傳統對數與離散對數的比較