第三章 數學基礎 例如 數論(Number Theory)，資訊理論(Information Theory)，複雜度理論 (Complexity Theory)，組合論(Combinatoric Theory)，機率(Probability)及線性代數 (Linear Algebra)等等數學理論.

Presentation on theme: "第三章 數學基礎 例如 數論(Number Theory)，資訊理論(Information Theory)，複雜度理論 (Complexity Theory)，組合論(Combinatoric Theory)，機率(Probability)及線性代數 (Linear Algebra)等等數學理論."— Presentation transcript:

1 第三章 數學基礎 例如 數論(Number Theory)，資訊理論(Information Theory)，複雜度理論 (Complexity Theory)，組合論(Combinatoric Theory)，機率(Probability)及線性代數 (Linear Algebra)等等數學理論 數論應是近代密碼學中(尤其是公開金匙密碼系統中)最重要的數學基礎。 2.0 群 (Group): (G, *) G: a set; *: an operation Associativity: a*(b*c) = (a*b)*c Identity: 1G, a G , such that 1*a=a*1=a Inverse: every element has inverse element. a G , a-1G, such that a* a-1 =1 Example: 1. (Z, +), I=0, (R-{0}, *) 3. (Zp*, *), ….. * Abelian group(Communicative group) 交換群  a*b=b*a or a+b=b+a Chap 3

2 有限場(Finite Field) 1) 正式的定義為，若一集合F在已定義的兩個運算“+”及“·”中， 具有下列性質者， 則F稱為一個場：
1. F在運算"+"中為一交換群(Abelian Group)，且具有單位元素0。 2. F- {0} 非零的元素在"·"中亦為交換群。(注意，交換群有反元素存在)。 3. F中"·"對"+"運算滿足分配律(Distributed Law)。即對於所有a, b, c, F，滿足 a · ( b + c )=a · b + a · c。 3) 一個場F，若其元素個數為無限多個，F稱為無限場(Infinite Field)。反之， 若F之元素為有限個，則稱為有限場(Finite Field)。 Chap 3

3 同餘及模運算 令三整數a, b及n 0，我們稱a在模n時與b同餘， a與b的差為n的整數倍。即a-b = kn，其中k為任一整數。
若a與b在模n中同餘，我們可寫成a ≡ b mod n。 由上述定義可知：若a與b在模n中同餘，則n必整除a與b之差，即n整除(a-b)，在符號上我們寫成 n|(a-b)。 剩餘類(Residue Class): 為n所整除之數為一剩餘類，以n整除餘數為1之數為一類，餘2之數為一剩餘類，以此類推。若將每一剩餘類中取一數為代表，形成一集合，則此集合稱為模n之完全剩餘系(Complete Set of Residues)，以Zn表示之。很明顯地，集合{0,1,2,…,n-1}為模n之一完全剩餘系。 5. 在同餘的基本運算中，存在以下之基本定理 定理(1)： a = a mod n(反身性)。 定理(2)： 若a = b mod n，則b = a mod n(對稱性)。 定理(3)︰ 若a = b mod n且b = c mod n，則a = c mod n(遞移性)。 定理(4)︰ 若a = b mod n且c = d mod n，則a + c = b + d mod n，a - c = b - d mod n，ac = bd mod n。 Chap 3

4 定理(5)︰ (a + b) mod n=[(a mod n) + (b mod n)] mod n，
定理(6)︰ 若ac = bd mod n且 c = d mod n及 (c, n) = 1， 則 a = b mod n。 ( (c, n)表示c及n之最大公因數，(c, n) = 1表示c與n互質)。 証︰由(a - b)c + b(c - d) = ac - bd = 0 mod n可得n|(a - b)c。 因為(c, n) = 1，故得n|(a - b)。因此a = b mod n。 (注意：定理(6)中，若c與n不互質，則此定理不成立。) 例如，3 × 2 = 1 × 2 mod 4 且 2 = 2 mod 4，但 3 1( mod 4)。 Chap 3

5 剩餘類 在模n的完全剩餘系中，若將所有與n互質的剩餘類形成一集合，則此集合稱為模n之縮剩餘 系(Reduced Set of Residues)，以 表示之。 例如n = 10時，{0,1,2,3,4,5,6,7,8,9} 為模10之完全剩餘系； 而 {1,3,7,9} 為模10之縮剩餘系。在模n中取縮剩餘系之原因，為在模n之縮剩餘系中取一整 數a，則必存在另一整數b(屬於此縮剩餘系)使得ab = 1 mod n且此解唯一。例如 其中"×"表示"無意義"。若ab = 1 mod n，則稱b為a在模n之乘法反元素，b可表示為a-1。定理(7) 說明上述之敘述為正確。 定理(7)︰若(a, n) = 1，則存在唯一整數b，0<b<n，且(b ,n)=1，使得ab = 1 mod n。 証：由定理(6)知，若(a, n) = 1，且i j mod n，則ai aj mod n。因此，集合{ai mod n}i=0,1,…,n-1 為集合{0,1,2,…,n-1}之一排列(Permutation)。因此b為ab = 1 mod n唯一解。此外，因ab - 1 = kn， k為整數，若(b, n) = g則g|(ab - 1)。因為g|ab，∴g|1。因此g = 1。故b亦與n互質。 定義(1)︰令Φ(n)為小於n，且與n互質的所有整數的個數。即Φ(n)為模n縮剩餘系中所有元素的 個數，此Φ(n)稱為尤拉商數(Euler Quotient Function)。 A 1 2 3 4 5 6 7 8 9 B × Chap 3

6 証：設(arj, n) = g，則 g|a或g|rj。因此我們得以下兩種情況： (1)g|a且g|n，或 (2)g|rj且g|n。
定理(8)︰令{ r1 ,r2 ,…,rΦ(n) }為模n之一縮剩餘系，且(a, n) = 1，則{ ar1, ar2 ,…,arΦ(n) } 亦為模n之一縮剩餘系。 証：設(arj, n) = g，則 g|a或g|rj。因此我們得以下兩種情況： (1)g|a且g|n，或 (2)g|rj且g|n。 (1)中不可能，因為(a, n) = 1。(2)中亦不可能，因為rj為模n縮剩餘系之一元素。因此(arj, n) = 1。此外，ari arj，若 ri rj。因此｛ar1, ar2 ,…,arΦ(n)｝為模n之一縮剩餘系。 定理(9)︰尤拉定理(Euler's Theorem) 若(a, n) = 1，則aΦ(n) = 1 mod n。 証︰令{ r1, r2 ,…, rΦ(n) }為模n之一縮剩餘系，由定理(8)知若(a, n)=1，則{ ar1, ar2 ,…,arΦ(n) }亦為一縮剩餘系。因此， 。故得(aΦ(n) mod n)( )= 。 由消去法(Cancellation)可得aΦ(n) mod n = 1。 例一：{1,3,5,7}為模8之一縮剩餘系，{3×1,3×3,3×5,3×7}亦為模8之一縮剩餘系。因此， (3 × 1)(3 × 3)(3 × 5)(3 × 7)=1 × 3 × 5 × 7 mod 8 34(1 × 3 × 5 × 7)= 1 × 3 × 5 × 7 mod 8 34=3Φ(8)=1 mod 8 Chap 3

7 定理(10)︰費瑪定理(Fermat's Theorem) 令p為一質數，且(a, p) = 1，則ap-1=1 mod p。
証：若p為質數，則Φ(p) = p-1，由尤拉定理可得証。 2.3 乘法反元素之求法 已給a及n且(a, n)=1，如何求a a-1=1 mod n？ 方法一： 若Φ(n)已知，則由尤拉定理可知aaΦ(n)-1=1 mod n。 因此，aΦ(n)-1 = a-1 mod n (注意：若n為質數，則Φ(n) = n-1為已知。若n為合成數，則Φ(n)不一定為已知 )。 方法二：利用歐基里德演算法(Euclidean Algorithm) 在中學數學中，我們已熟知利用歐基里德演算法求兩整數a及n之最大公因數 (Greatest Common Divisor , gcd)。我們首先介紹，利用歐基里德演算法求gcd之方法。 refer to textbook for detail Chap 3

8 rj-2 = rj-1gj-1 + rj 0 rj < rj-1，
令r0 = n, r1 = a，n a，利用連續除法可得 r0 = r1g1 + r r2 < r1， r1 = r2g2 + r r3 < r2， ﹕ rj-2 = rj-1gj-1 + rj rj < rj-1， rm-4 = rm-3gm-3 + rm rm-2 < rm-2， rm-3 = rm-2gm-2 + rm rm-1 < rm-2 ， rm-2 = rm-1gm-1 + rm rm < rm-1， rm-1 = rmgm 則rm為a及n之最大公因數。歐基里德演算法求gcd之主要觀念在於，若c = dg + r，則(c, d) = (d, r)。因此在上述演算法中，(a, n) = (r0, r1) = (r1, r2) = … = (rm-1, rm) = (rm, 0) = rm。歐基里德演算法亦可以求出兩個整數s及t使得sa + tn = (a, n) (注意s及t並非唯一)滿足上述者我們稱為(a, n)為a, n之線性組合。 其方法為 rm = (a, n) = rm-2-rm-1gm-1 ，因此(a, n)為rm-2及rm-1之線性組合。由於rm-1 = rm-3-rm-2gm-2, 代入上式得 (a ,n) = rm-2-(rm-3-rm-2gm-2)gm-1 = (1 + gm-1gm-2)rm-2-gm-1rm-3 Chap 3

9 因此(a, n)為rm-2及rm-3之線性組合。以此反推回去，我們可得(a, n) = sa + tn。若(a, n) = 1，則1 = sa + tn。所以sa = 1 mod n，因此s = a-1 mod n。 Knuth[1]已証明，利用歐基里德求模n之乘法反元素，平均約需0.843ln(n)+1.47次除法。而利用方法一之尤拉定理，平均約需1.5 log2n-2乘法。因此，求乘法反元素以方法二為較佳。 Chap 3

10 (2) 若(M, n) 1，則上述亦成立唯証明較複雜，請參閱 [5]。
定理(11)︰令n>0且(e, Φ(n)) = 1。設d滿足ed = 1 mod Φ(n)。令E(M)=Me mod n且D(C) = Cd mod n，則D(E(M)) = E(D(M)) = M mod n。 証︰對於所有0 < M < n。 (1) 若(M, n) = 1則D(E(M)) = (Me mod n)d mod n = Med mod n = M tΦ(n)+1 mod n = M mod n。同樣地，可得E(D(M)) = M。 (2) 若(M, n) 1，則上述亦成立唯証明較複雜，請參閱 [5]。 模n之完全剩餘系Zn在加法中為一交換群，且單位元素0存在。 模n之縮剩餘系 在乘法中為一交換群。 Chap 3

11 線性同餘 已給整數a, b及n>0，下式稱為單變數同餘式(Linear Congruence in One Variable)
ax = b mod n 其中x為變數。 定理(12)：令a, b及n為整數，且n>0及(a, n) = d。 (1) 若d | b，則ax = b mod n無解。 (2) 若d|b，則ax = b mod n恰有d個模n不同餘類的解。 証：由定義知，線性同餘式等於求兩變數x及y滿足ax – yn = b。整數x為ax = b mod n之一解，若且唯若存在整數y，使得ax – yn = b。當d | b時，因d|ax及d|yn，使得d|(ax-yn)，當d | b時，ax – yn = b無解。當d|b時ax – yn = b，有無限多解。因為若x0及y0為一解時，所有 x = x t ， y = y t 均為其解，其中t為任意整數。但上述解中祇有d個模n的不同餘類，因為 t mod n中祇有d個不同的同餘類，即t = 0 ,1 ,2 ,…,d-1。 由本定理知，若(a, n) = 1，則ax = b mod n有唯一解。 Chap 3

12 定理(12)祇告訴我們線性同餘式ax = b mod n是否有解，及若有解時，有多少個解 。以下我們介紹當有解時，如何求出其解：
(1) 利用歐基里德演算法求出(a, n) = d，若d | b，則上式無解。 (2) 若d|b，則令a'= ，b'= ，n'= 。則 a'x' = b' mod n'中有唯一解，因為(a', n')=1。 此解可以由歐基里德演算法求出。例如，先求a'為模n'之乘法反元素(a')-1，令x' = (a')-1 b' mod n'即為其解。接著令x0 = x' mod n，則x0即為ax = b mod n之一解。令x = x t mod n，t = 0, 1, 2, …,d-1, 則所有d個解均可求出。 例二：求解9x = 12 mod 15。 解︰ (1) (9, 15) = 3且3|12，故有3個解。 (2) 求解3x' = 4 mod 5，由於3‧2 = 1 mod 5 ,故3 –1 = 2 mod 5。∴x' = 2‧4 = 3 mod 5。令x = x0 = 3 mod 15 且 x = x0 + 5 = 8 mod 15，x = x0 + 5‧2 = 13 mod 15，此為所有3個解。 Chap 3

13 中國餘數定理(Chinese Remainder Theorem)
定理(13)：令n1, n2 ,…,nt為兩兩互質之正整數，令N = n1n2…nt。則以下同餘系統中，x = a1 mod n1，x = a2 mod n2，…，x = a t mod n t，會在[0 , N-1]中有唯一解。 証：由於n1 ,n2 ,…,nt為兩兩互質，故對所有i=1, 2, … ,t , = 1。因此，存在yi，使得 yi = 1 mod ni。此外， yi = 0 mod nj，當j i，此乃由於 為nj之整數倍。若我們令 x = y1a y2a2 + … ytat mod N = [ ] mod N 則x為上述同餘系統之解，因為對於所有i, 1 i t，x mod ni = yiai mod ni = ai。 若上述同餘系統有兩個解為x及z，則對所有i, 1 i t，滿足x = z = ai mod ni，故ni|(x-z)。因此，N|(x-z)，即x = z mod N。因此，此系統有唯一解。 註：中國餘數定理最早記載於第一世紀之孫子算經中[8]，為線性同餘式之濫觴， 故名之為中國餘數定理。其原問題為：今有物不知其數，三三數之賸二，五五數之賸三，七七數之賸二，問物幾何？ 即求正整數x滿足 x = 2 mod 3， x = 3 mod 5， x = 2 mod 7。 Chap 3

14 解：首先求出u滿足 u‧n2 = 1 mod n1，接著 (1) 若a1 (a2 mod n1) ,
例三：求x滿足上式。 解：N=3‧5‧7 = 105， ， ， ， ∴由 35y1 = 11 mod 3， 得y1 = 2。 由 21y2 = 1 mod 5，得y2 = 1。 由 15y3 = 1 mod 7，得y3 = 1。 故 x = 35‧2‧2 + 21‧1‧3 + 15‧1‧2 = 23 mod 105 中國餘數定理在密碼學上有非常重要的應用。例如在RSA解密時，利用中國餘數定理，可以使解密速度加快約4倍[4]。以下我們介紹求解t = 2時，較快速的方法。此方法較定理(13)之標準解法，可節省約一半的計算時間。 例四：已給a1, a2, n1及n2, 且n1<n2 , 及(n1, n2) = 1 ,求x使得0 x < n1n2，滿足 x = a1 mod n1 = a2 mod n2。 解：首先求出u滿足　u‧n2 = 1 mod n1，接著 (1) 若a1 (a2 mod n1) , 則x = (((a1 - (a2 mod n1)) × u) mod n1) × n2 + a2 (2) 若a1< (a2 mod n1) , 則x = (((a1 + n1 - (a2 mod n1)) × u) mod n1) × n2 + a2 Chap 3

15 二次剩餘(Quadratic Residue)
二次剩餘在機率式密碼系統、質數測試、分解因數等，均佔有很重要的地位。 定義(2)︰令n為正整數，若整數a，(a, n)=1，滿足x2 = a mod n有解，則稱a為模n之二次剩餘(Quadratic Residue of n)。否則a稱為模n之非二次剩餘(Quadratic Nonresidue of n)。 我們通常以符號QRn表示所有模n之二次剩餘的集合。以QNRn表示所有模n之非二次剩餘之集合。 例五︰若n = 7，模n之二次剩餘有{12,22,32,42,52,62 }mod 7 = {1,2,4}，其餘{3,5,6}為非二次剩餘，因為無法找到整數解滿足x2 = a mod 7，a {3,5,6}。 定理(14)：令p為奇質數，且0 < a < p，則 (1) 若a QRp，則x2 = a mod p有二個解。若a QNRp，則無解。 (2) 令p為奇質數，則 |QRp| = ，且 |QNRp| = 。其中 |QRp| 表示集合QRp之元素個數。 証： (1) 若a QRp，則 x2 = a mod p至少有一解x1。但 p-x1 亦為其解，因為 (p - x1)2 = (p2-2px1 + x12) mod p = x12 = a mod p，且對於p > 2，p - x1 x1，故得証。 (2) 明顯地，12, 22, …, mod p均為二次剩餘。此外，並無其他二次剩餘。因為，若 a QRp，則至少其平方根x1，或p-x1，必落在[1, ]範圍中。 Chap 3

16 定理(15)︰若p為奇質數，且0 < a < p，則
証：由費瑪定理知a p = 0 mod p。 若p為奇數，則上式可分解成 。 此意味著p可整除 或 。即 ，或 。若a QRp，則存在x，使得x2 = a mod p，因此， = x p-1 mod p = 1 mod p 故 有 解。但因其次數(degree)為 ，故最多僅有 解。其餘的 個非二次剩餘，必為 之解。 定義(3)：雷建德符號(Legendre Symbol) 若p為奇質數，且0 < a < p，雷建德符號 定義為 註：(1) 由定理(15)，可求出 。若p不是質數則稱為加寇比符號。 (2) 無意義。 Chap 3

17 定義(4)：加寇比符號(Jacobi Symbol)
令n為奇正整數，且n = p p … p 。其中pi為質數，ti 0。令整數a與n互質，則加寇比 符號定義為 以下是加寇比符號之性質。在此，n為正奇整數，且a與b 均與n互質，有興趣的讀者請參閱[6]。 性質(1) 當n為奇質數時， 。 (2) 。 (3) 。 (4) ， 即若n = 1 mod 8 或 n = 7 mod 8 則 J( ) = 1， 即若n = 3 mod 8 或 n = 5 mod 8 則 J( ) = -1， (5) 。 (6)若(a, b) = 1，則J( )J( )= 。 Chap 3

18 由於雷建德符號為加寇比符號之特殊狀況(n為奇質數)，故上述性質亦存在於雷建德符號中。
由雷建德符號之定義及定理(15)可知，求雷建德符號祇需一次指數模乘法。 由加寇比符號之定義知，若我們能分解因數n = p p … p ，為使n成為所有質數的乘積，則 求加寇比符號祇需最多m次指數乘法。事實上，利用性質(3)及(6)，我們可以更快速地求得加寇 比符號J( )。 問題一︰若我們無法分解因數n，是否我們仍能快速求出J( )？ 定理(16)告訴我們其答案是肯 定的，其証明請參閱[6, p.330]。 定理(16)︰令a , n為正整數，且 ( a , n ) = 1，則J( )可以在O((log2n)3)位元運算中(相當於指數運 算)求出。有關符號O之定義請參閱3.2複雜度簡介。 性質(3)提供我們一個很重要的事實：設p為奇質數，令c = ab (mod p)，則若 (1) a QRp且b QRp，則c QRp， (2) a QRp且b QNRp，則c QNRp， (3) a QNRp且b QRp，則c QNRp， (4) A QNRp且b QNRp，則c QRp。 Chap 3

19 問題二： 若J( )=1，是否表示x2 = a mod n均有解？
此問題之答案為︰否定。(注意若( )=1，則答案為︰肯定)。其原因為，若J( )= ，並不表示所有 ，i = 1,2,… m。 例如J( ) = = (-1)(-1) = 1。但因x2 = 2 mod 3，及x2 = 2 mod 5均無解 ，故x2 =2 mod 15亦 無解。例如 J( )=1，但因x2 = 1 mod 3，及x2 = 1 或5均有兩個解。故 x2 =1或15有4個解： x=1,x=4,x=11,x=14。 當n=pq，p及q均為兩大質數時，為近代密碼學中最重要的應用。例如RSA系統即為此種情況。 當n = pq時之二次剩餘，有以下重要定理。 定理(17)︰設p及q均為奇質數且n = pq，令a ，則 (1) a為模n之二次剩餘，若且唯若a為模p之二次剩餘，且a為模q之二次剩餘。 (2) 若a為模n之二次剩餘，則z2 = a mod n在 中有四個解，表示為{x,n-x,y,n-y}。我們通常將 {x,n-x}表為一組解，{y,n-y}表為另一組解。 (3) 若n為模n之二次剩餘，且p及q均為已知，則z2 = a mod n之四個解均可在多項式時間內求出。 (4) 若a為模n之二次剩餘，則若我們已知z2 = a mod n二組解中之任一解，則n可在多項式時間 內分解因數p及q。 Chap 3

20 (2)、由定理(14)(1)知，a在模p中有二個解{x'及-x'}，a在模q中有二個解{y',-y'}。 因此w滿足下列四式其中之一︰
証：(1)、 設a為模p及模q之二次剩餘，則存在r ，t ，使得r2 = a mod p，及t2 = a mod q。由中國餘數定理知，必存在w Zn，滿足w = r mod p，且w = t mod q。故w2 = a mod p，且w2 = a mod q。因此，w2 = a mod n。故a為模n之二次剩餘。另一方面，令ap = a mod p ， aq = a mod q，因a ，故a p 及aq 。令w2 = a mod n，w ，則w2 = ap mod p，且w2 = aq mod q。故ap及aq分別為模p及模q之二次剩餘。 (2)、由定理(14)(1)知，a在模p中有二個解{x'及-x'}，a在模q中有二個解{y',-y'}。 因此w滿足下列四式其中之一︰ (1) w = x' mod p 或 (2) w = x' mod p w = y' mod q w = -y' mod q (3) w = -x' mod p 或 (4) w=-x' mod q w = y' mod q w=-y' mod q 由中國餘數定理知，w2 = a mod n最多有4個根。此外，(1)及(4)之解恰為一組即{x,n-x}，(2)及(4) 之解恰為一組，即{y , n-y}。且均不相同，故恰有四個解。 (3)、由於p及q均為質數，因此w2 = ap mod p，及w2 = aq mod q之解{x', -x'}及{y', -y'}均可在多項 式時間內求出。利用中國餘數定理，(2)中四種情況之解，均可在多項式時間內求出(將於以後 討論)。 Chap 3

21 (4)、若已知z2 = a mod n二組解，且各為{x, n-x}及{y, n-y}中之任一解，例如x及y，則x及y滿足 及 故 或
所以q|x + y，p|x - y。故(x + y, n) = q，(x - y, n) = p，因此最大公因數可在 多項式時間內求解，故得証。 註： (1) 若已知同一組解之二解，{x, n-x}或{y, n-y}，並無法分解因數。因GCD (x + (n-x), n) = n或 GCD(x - (n-x), n) = 1。 (2) 若已知z 2 = a mod n 4個解中之任二解，則能在多項式時間內分解因數n之機率為 。因為， 此二解分屬不同組之機率為 。 由定理(17)可知，若n為兩大奇數之乘積，即n = pq，設En (x) = x2 mod n，則E n(x)為一個4對1函 數，因為有4個x 會對應至相同的值En(x) = a = x2 mod n。若a在模n為二次剩餘，且p, q為已知， 則可在多項式時間內求出其4個解。由定理(18)知，若p, q為未知，則欲求一模n之二次剩餘a的平 方根，x滿足x2 = a mod n的困難度，等於分解因數n。因此En(x)若在不知p及q情況下為一單向函 數，若已知p及q，則En(x)非為單向函數，此種函數可稱為單向暗門函數(p及q為暗門)。 Chap 3

22 設n = pq，為兩奇質數之乘積，若x ，由於加寇比符號 J( ) = J( )J( )=( )( )，
定理(18)︰已給n=pq，p、q為兩大質數且為未知，若有一演算法AL，可在任給模n之二次剩 餘a時，求出其任一平方根滿足x2 = a mod n，則AL可在多項式時間內分解因數n。 証：我們可任選一整數x1<n，若x1不與n互質，則求x1與n之最大公因數即可得p或q，故可在 多項式時間內分解n 。若x1與n互質，則我們求出x = a mod n，並利用AL求解a之平方根x， 若x與x1為二組解中之同一組解，則我們無法分解因數n，但若x與x1為二組解中之不同一組解， 則由定理(17)我們可分解因數n,故成功之機率為 。但重覆上述步驟t次，則我們可分解因數n 之機率，大於等於1-2-t。因此 利用AL我們可在多項式時間內分解因數n。 設n = pq，為兩奇質數之乘積，若x ，由於加寇比符號 J( ) = J( )J( )=( )( )， 因此，當J( ) = 1，則( ) = 1且( ) = 1， 或( ) = -1 且( ) =-1。 當J( ) = -1，則( ) = 1 且( ) = -1， 或( ) = -1 且( ) = 1。 Chap 3

23 因此， 依加寇比符號可以被分成下列四類。如表2.1所示。
因此， 依加寇比符號可以被分成下列四類。如表2.1所示。 表 依加寇比符號將分成四類 J( ) J( ) 1 Q00(n) -1 Q11(n) Q01(n) Q10(n) Qij(n) 在上述分類中，祇有x Q00(n)時，x才是模n之二次剩餘。若x屬於其他三類時，則x為非 二次剩餘。由於J( )=1或-1可在不需知p及q情況下於多項式時間內求解。因此當 x Q01(n)或Q10(n)時我們可在多項式時間內判斷其為非二次剩餘。若x Q00(n)或Q11(n) 則我們無法在多項式時間內判斷x是否為二次剩餘，除非我們能求出p及q。 由加寇比符號之性質(3)，若n=pq，且p, q>2，則我們有以下結果： (1) 對於x,y ，xy mod n為模n之二次剩餘，若且唯若x及y屬於相同的Qij(n)。 (2) 兩二次剩餘之乘積，為二次剩餘。 (3) 二次剩餘與非二次剩餘之乘積，為非二次剩餘。 Chap 3

24 (2) 若x,y ，滿足x2 = y2 mod n，且x y或 -y mod n，則J( ) = -J( )
若n = pq，且p = 3 mod 4及q = 3 mod 4，則n稱為布倫(Blum)整數。當n為布倫整數時，其二次 剩餘具有以下有趣的性質： (1) J( ) = J( ) (2) 若x,y ，滿足x2 = y2 mod n，且x y或 -y mod n，則J( ) = -J( ) (3) 若a為模n之二次剩餘，則x2 = a mod n之4個解恰好在Q00(n), Q11(n), Q10(n), Q01(n)中各有一解。 証： (1) 由於p=3 mod 4，且q = 3 mod 4，則( ) = = -1，且( )= = -1，故J( ) = ( )( ) = (-1)(-1)=1。所以，J( ) = J( )J( )=J( )。 (2) 若x2 = y2 mod n，則x2 = y2 mod p且x2 = y2 mod q。故(x-y)(x+y) = 0 mod p。因此，x = dy mod p，d為1或-1，相同地。x = ey mod q，e = 1或-1。由於 。 若e = d，則y = dx mod p及y = dx mod q。故y = dx mod n。但因y x或-x mod n，此與假設矛盾。 故e d。因此，J( ) = J( )J( )J( ) = -J( )。 Chap 3

25 (3) 令{x, n-x, y, n-y}為a模n之4個平方根。由於n-x = -x mod p，故J( ) = -J( )。相同地， J( ) = -J( )。因此，若x Qij(n)，則n-x Q1-i,1-j(n)。此在y及n-y中亦存在。由上述性質(2) 知，若x2 = y2 mod n, 且y x或 -x mod n，則J( ) = -J( )。因此，x與y不能在同一類Q(n)， 故y及n-y需在Qi,1-j(n)及Q1-i,j(n)中。故a之4個平方根中恰好在Qij(n)，i = 0或1，j = 0或1中，各 有一解。 Chap 3

26 輸入：質數p(=3 mod 4)及模p之二次剩餘a。 輸出： x滿足x2=a mod p。 步驟(1)：求 。 步驟(2)：輸出x。
方法一： 輸入：質數p(=3 mod 4)及模p之二次剩餘a。 輸出： x滿足x2=a mod p。 步驟(1)：求 。 步驟(2)：輸出x。 上述步驟(1)中，若x2=a mod p，則 由於不論是x或-x，均是a在模p中之平方根(定理14)，故方法一為正確。 當p = 1 mod 4之質數時，迄今並無類似方法之確定式演算法存在。Peralta[9]在1986年提 出一個非常簡單的演算法可求出a的平方根，此方法為機率式演算法，有興趣之讀者請 參閱原論文(註：本方法不論p為何種形式均可求解) Chap 3

27 步驟(1)：任選一整數r，若r2 = a mod p，輸出x = r。 步驟(2)：計算
方法二： 輸入：質數p及模p之二次剩餘a 輸出：x滿足x2 = a mod p 步驟(1)：任選一整數r，若r2 = a mod p，輸出x = r。 步驟(2)：計算 步驟(3)：若u = 0，則輸出x = v -1 mod p，否則重覆步驟1。 上述步驟(2)中y為一符號，相當於在複數中之i，(b + cy)(d + ey)= (bd + cey2) + (be + cd)y = (bd + cea) + (be + cd) y mod y2-a。 由於a為模p之二次剩餘，因此f(y) = y2-a = (y + x)(y - x)。故f(y)並不是不可分解多項式， 因此，其運算雖與GF(p2)類似，但在f(y)中並不是有限場。Peralta已証明，每一次任選r， 本演算法可求出x之機率，大於或等於 。 例八：求x使其滿足x2 = 12 mod 13。 解： (1) 任選r=3，32=9 12，故進行步驟(2)求 。因為 ， 故重覆步驟(1)。 (2)任選r = 7，72 =49 12，故進行步驟(2)求(7+y)6=0+8y mod y2-12。 故x=8-1=5 mod 13。 Chap 3