An toán thông tin - Toán học dùng cho mật mã

Nội dung text: An toán thông tin - Toán học dùng cho mật mã

1. Nội dung .Số học số nguyên (Integer Arithmetic) ◦Phép chia hết ◦Giải thuật Euclid m gcd .Số học đồng dư (Modular Arithmetic) ◦Các lớp đồng dư ◦Nghịch đảo cộng vànhân modulo n 2
2. Nội dung .Algebraic structures ◦Group và Field ◦GF(2) vàGF( 2n) .Số nguyên tố (prime) ◦Hàm Phi Euler ◦Định lýFermat vàEuler .Các bài toán khó giải 3
3. Dẫn nhập .Lý thuyết mật mã sử dụng và gắn liền vớirấ t nhiều kiến thức toán học, bao gồm: ◦Lý thuyết số ◦Lý thuyết thông tin ◦Độ phức tạp tính toán ◦Thống kê ◦Tổ hợp. 4
4. Phần I : Integer Arithmetic 5
5. Số học số nguyên Integer Arithmetic .Tập các số nguyên Z ={ ., -2,-1,0,1,2, } .Tập các số nguyên không âm Z+ = {0,1,2, } .Tập các số tự nhiên N= {0,1,2, } .Tập các số tự nhiên khác không N+ = N \ {0} 6
6. Tính chia hết của các số nguyên .Tập Z là đóng kín với các phép toán +, - và* nhưng không đóng kín với phép chia ◦Phép cộng a+b ◦Phép trừ a – b kết quả là1 số nguyên Z ◦Phép nhân a * b ◦Nhưng phép chia a /b có thể không là 1 số nguyên 7
7. Tính chia hết của các số nguyên . 8
8. Định lý phép chia của Euclid .Đối với mọi số n, d ∈ Z\{0} luôn tồn tại duy nhất các số q, r ∈ Z sao cho n = qd + r với 0 ≤ r< |d| .n là số bị chia (dividend), d là số chia (divisor), q là thương số (quotient) và r làsố dư (remainder) ký hiệu là Rd(n) .Ví dụ : R7(16) = 2 (vì 16 = 2 x 7+2) R7(−16) = ?? 5 (vì− 16 = −3 x 7+5) R7(1) = R7(8) = R7(15) = R7(22) =1. 9
9. Lưu ý .Khi chúng ra tính bằng máy tính hặc máy tính tay, r và q ra số âm (negative) khi a là số âm. Làm thế nào để chúng ra có thể ngăn chăn điều này bởi vì r phải là số không âm? .Giải pháp rất đơn giản, chúng ta giảm giá trị của qbởi1 và chúng ta có thêm giá trị của n thêm r để làm cho nó dương. 10
10. Ước số chung lớn nhất (Greatest Common Divisor –gcd) .Cho hai số a, b ∈ Z \{0}, c ∈ Z là ước số chung (common divisor) của a vàb nếu c|a vàc|b .C được gọi là ước số chung lớn nhất (greatest common divisor), ký hiệu gcd(a, b), nếu nó làsố nguyên lớn nhất được chia hết bởi cảa và b. .Ví dụ: gcd(12,18) =6, gcd(-18,27) = 9 11
11. Thuật toán Euclid tìm gcd .Thuật toán dựa trên2 lập luận: gcd (a, 0) = a gcd (a, b) = gcd (b, r), với r là phần dư của a chia cho b Ví dụ: gcd (36, 10) = gcd (10, 6) = gcd (6, 4) = gcd (4, 2) = gcd (2, 0) = 2 để tính gcd(36,10), ta chỉ cần tìm gcd(2,0) 12
12. Thuật toán Euclid tìm gcd(a,b) 13
13. Ví dụ: Tìm gcd(2740,1760) gcd (2740, 1760) = 20 14
14. Ví dụ: Tìm gcd(25,60) . gcd(25,60)=5 15
15. Thuật toán Euclid mở rộng (extended Euclidean algorithm) .Cho 2 số nguyên a và b, tìm2 số nguyên khác s và t sao cho: .Thuật toán này vừa cóthể nh được gcd(a,b) vừa nh được các giá trịs vàt 16
16. Thuật toán Euclid mở rộng (extended Euclidean algorithm) 17
17. Thuật toán Euclid mở rộng (extended Euclidean algorithm) 18
18. Ví dụ: a = 161 và b = 28, tìm gcd (a, b) và giá trị s và t. Giải: r = r1− q × r2; s = s1−q × s2; t = t1− q × t2 gcd (161, 28) = 7, s = −1 và t = 6. 19
19. Nguyên tố cùng nhau (co-prime hay relatively prime ) .Hai số nguyên a, b ∈ Z \{0} được gọi là nguyên tố cùng nhau nếu gcd(a, b)=1. .Ví dụ: (5,8) , (9,14) là các cặp nguyên tố cùng nhau 20
20. Phần ii: Modular Arithmetic 21
21. Modulo Operator .Phép modulo được ký hiệu làmod . Ngõ ra r được gọi là thặng dư (residue). 2.22
22. Đồng dư theo modular (modular congruence) .Cho hai số a, b ∈ Z vàn ∈ N. Số a được gọi là đồng dư (congruent) với b theo modulo n nếu n|a − b .Ký hiệu a ≡ b (mod n) .Ví dụ: 7 ≡ 12 (mod 5), 4 ≡−1(mod 5), 12 ≡ 0(mod 2), −2 ≡ 19 (mod 21). 23
23. Tính chất của đồng dư modular n .Với mọi số n ∈ N và a, b, c ∈ Z, các nh chất sau luôn thỏa mãn: 1. a ≡ a (mod n) (nh phản xạ) 2. Nếu a ≡ b (mod n) thì b ≡ a (mod n) (nh đối xứng) 3. Nếu a ≡ b (mod n) and b ≡ c (mod n) thì a ≡ c (mod n) (nh bắc cầu) 24
24. Quan hệtương đương (equivalence relation) .Theo nh chất của quan hệtương đương trên 1 tập nào đó thì tập đó được phân hoạch (partitions) thành 1 tập các lớp tương đương (equivalence class), được gọi là các lớp thặng dư (residue class). .Quan hệ đồng dư theo modular n làquan hệtương đương 25
25. Quan hệtương đương (equivalence relation) .Ký hiệu Rn(a) để chỉ lớp đồng dư chứa tất cả các số x ∈ Z đồng dư với a theo modulo n .Rn(a) còn được ký hiệu là a hay a nZ .Ví dụ: R4(1) = {1, 5, 9, 13, 17, } 26
26. Tập các thặng dư nhỏ nhất .Trong mỗi lớp đồng dư luôn có1 phần tửkhông âm nhỏ nhất được gọi là least residue. Trong lớp [0] least residue là 0, [1] least residue là1 , .Tập hợp tất cả các least residue modulo n Zn={0,1,2,3, , n-1} được gọi làset of all least residue modulo n 27
27. Các phép toán đồng dư .3 phép toán: Addtion,subtraction, và multiplication 28
28. Các phép toán đồng dư Ví dụ: .Cộng 7 với 4 trong Z15 .Trừ 11 từ 7 trong Z13 .Nhân 11 bởi 7 trong Z20 Giải: .(14 + 7) mod 15 → (21) mod 15 = 6 .(7 − 11) mod 13 → (−4) mod 13 = 9 .(7 × 11) mod 20 → (77) mod 20 = 17 29
29. Các phép toán đồng dư: Thuộc tính 30
30. Các phép toán đồng dư Ví dụ: .R7(12 + 18) = R7(R7(12) + R7(18)) = 2 .R7(12 · 18) = R7(R7(12) · R7(18)) = R7(5 · 4)= R7(20) = 6 31
31. Các số nghịch đảo .Khi thực hiện các phép toán số học modular, thường phải m nghịch đảo của 1 số tương ứng với phép toán. ◦Nghịch đảo cộng (additive inverse) ◦Nghịch đảo nhân (multiplicative inverse) 32
32. Nghịch đảo cộng Additive Inverse .Trong Zn, hai số a vàb là nghịch đảo cộng (additive inverse) của nhau nếu Lưu ý Trong phép toán đồng dư, mỗi số nguyên đều có một nghịch đảo cộng. Tổng số nguyên và nghịch đảo cộng của nó đồng dư với0 modulo n. 2.33
33. Ví dụ .Tìm tất cả các cặp nghịch đảo cộng trong Z10. .Có 6 cặp nghịch đảo cộng của nhau trong Z10 là (0, 0), (1, 9), (2, 8), (3, 7), (4, 6), and (5, 5). 2.34
34. Nghịch đảo nhân multiplicative inverse .Nếu tồn tại 1 số b ∈ Zn sao cho ab ≡ 1(mod n) thì b được gọi là nghịch đảo nhân của a modulo n .Ký hiệu 35
35. Nghịch đảo nhân multiplicative inverse .Điều kiện để số a có nghịch đảo nhân khi và chỉ khi gcd(a, n)=1 .Ví dụ: a=22, n=25 Gcd(22,25)= 1 a có nghịch đảo nhân 8 = 22-1 (mod 25) vì 8.22 = 176 = 1 (mod 25) 8 là nghịch đảo nhân của 22 modulo 25 36
36. Ví dụ nghịch đảo nhân .Cho n = 5 và a = 2. Vì gcd(2, 5) = 1, do đó 2 sẽ có nghịch đảo nhân modulo 5 3 = 2-1 (mod) 5 vì 2·3 ≡ 1 (mod 5). .gcd(4, 15) = 1 vì vậy4 có nghịch đảo nhân modulo 15. Vì 4 · 4 ≡ 1 (mod 15) nên 4 = 4-1 (mod 15) 37
37. Cách tìm nghịch đảo nhân .Cách 1: dùng giải thuật Euclid mở rộng au + pv = 1 với u,v số nguyên u=a-1 mod p .Cách 2: dùng giải thuật nh số mũnhanh (với p là số nguyên tố) a1  ap-2 (mod p) 38
38. Nghịch đảo nhân multiplicative inverse .Để nh nghịch đảo nhân modulo n, áp dụng giải thuật Euclid mở rộng: s x n + t x b = gcd(n,b) =1 .Thực hiện phép mod cả2 vế (s x n + t x b) mod n = 1 mod n [(s x n) mod n] + [(txb) mod n] = 1 mod n 0 + [(txb) mod n] = 1 ( t x b ) mod n = 1 t chính là nghịch đảo nhân của b 39
39. Ví dụ: Tìm nghịch đảo nhân của 23 trong Z100. t = t1− q × t2 . gcd(100, 23) là 1; nghịch đảo nhân của 23 là -13 hoặc 87. 40
40. Ví dụ: Tìm nghịch đảo nhân của 12 trong Z26. .gcd(26, 2) là 2; nghịch đảo nhân không tồn tại 41
41. Ví dụ: Tìm nghịch đảo nhân của 7 trong Z160 42
42. Các tập hợp nghịch đảo cộng & nhân . Zn = {0,1, ,n-1} .Nếu n làsố nguyên tố thì . làtậ p hợp tất cảcá c số thuộc Zn khả nghịch modulo n .Mỗi phần tử của Zn đều có nghịch đảo cộng, nhưng chỉ có 1 số là cónghị ch đảo nhân. Mỗi phần tử của đều có nghịch đảo nhân nhưng chỉ có 1 số là cónghị ch đảo cộng. 43
43. Ví dụ tmộ số tập hợp Zn vàZn * 44
44. Phần IV SỐ NGUYÊN TỐ (PRIME) 45
45. Nguyên tố và hợp số .Số tự nhiên (natural number) 1 <n ∈ N được gọi là số nguyên tố (prime) nếu nó chỉchia hết cho chính nó và cho 1. .Số tự nhiên n ∈ N không phải là số nguyên tố thì được gọi là hợp số (composite) .Tập hợp các số nguyên tố được ký hiệu là P .Lưu ý: Số 1 không phải là số nguyên tố̀ cũng không phải là hợp số 46
46. Hàm đếm các số nguyên tố .Hàm đếm các số nguyên tố (prime counting function) π(n) cho kết quả là số các số nguyên tố nhỏ hơn hay bằng n ∈ N π(n):= |{p ∈ P | p ≤ n}| 47
47. Euler’s Phi Function .Dùng để đếm các số nhỏ hơn n ∈ N mànguyên tố cùng nhau với n (n)=|{a {0, ,n-1}| gcd(a, n)=1}| .Ví dụ: (10) = 4 48
48. Euler’s Phi Function 1. (1)=0 2. (p)=p-1 nếu p là một nguyên tố 3. (m x n)=(m) x (n) nếu m và n là nguyên tố cùng nhau 4. (pe)=pe-pe-1 nếu p là một nguyên tố 49
49. Euler’s Phi Function .Kết hợp 4 quy tắc trên, nếu với mọi số nguyên n có thể phân ch thành thừa số (factorize) nguyên tố Thì .Ví dụ: φ(45) = φ(32.5) = (3-1).32-1.(5-1).51-1=24 50
50. Ví dụ: Giá trị của (240)? Giải Chúng ta có thể viết 240 = 24 × 31 × 51. thì (240) = (2-1) x (24-1 ) x (3-1) × (31-1) × (5-1)(51-1 ) = 64 51
51. Ví dụ: Chúng ta có thể nói (49) = (7) × (7) = 6 × 6 = 36? Giải .Không. Vì 7 và 7 không là nguyên tố cùng nhau nên không áp dụng được luật 3. .49 = 72, chúng ta cần luật thứ 4: (49) = 72 − 71 = 42. 52
52. Ví dụ: Tính (187), với 187 = 17 x 11 53
53. Lưu ý Độ khó của việt tìm (n) tùy thuộc vào độ khó của việc phân tích thừa số của n. 54
54. Định lý Little Fermat (1640) . Nếu p là1 số nguyên tố và a là số nguyên thì ap-1 = 1 mod p . Hoặc ap ≡ a mod p . Ví dụ: cho p=5 34 = 81 = 1 mod 5 . Ứng dụng: dùng để nh nghịch đảo nhân nhưng không hiệu quả bằng giải thuật Euclid mở rộng p-2 −1 p-2 Vì x ∈ Zp ⇒ x⋅x = 1 ⇒ x = x in Zp 55
55. Định lýEuler .Định lýEuler được xem như trường hợp đặc biệt của định lýFermat .First Version a(n) ≡ 1 (mod n) .Second Version a k × (n) + 1 ≡ a (mod n) 9.56
56. Tìm nghịch đảo nhân dùng định lýEuler .Định lýEuler có thể được dùng để m nghịch đảo nhân modulo 1 hợp số. a−1 mod n = a(n)−1 mod n 9.57
57. Ví dụ: .The answers to multiplicative inverses modulo a composite can be found without using the extended Euclidean algorithm if we know the factorization of the composite: 58
58. Example 9.17 The answers to multiplicative inverses modulo a composite can be found without using the extended Euclidean algorithm if we know the factorization of the composite: 9.59
59. Phần tử đồng nhất Identity element .Cho S là 1 tập hợp và ∗ là phép toán hai ngôi (binary operation) trên S. Phần tử e∈ S được gọi là phần tử đồng nhất nếu luôn có e ∗ a = a ∗ e = a  a ∈ S Ví dụ: phần tử đồng nhất của phép cộng và phép nhân trong Z?? số 0 là phần tử đồng nhất của phép cộng, số 1 là phần tử đồng nhất của phép nhân trong Z
60. Groups .Group (G): tập hợp các phần tử với 1 phép toán 2 ngôi “” và thỏa mãn 4 thuộc nh sau: ◦Closure: nếu a,b G thì c=a  b G ◦Associativity: nếu a,b G thì (a  b)  c = a  (b  c ) ◦Existence of identity: a G luôn tồn tại 1 phần tử e được gọi là phần tử đồng nhất (identity element) sao cho e  a= a e = a ◦Existence of inverse: a G luôn tồn tại 1 phần tử a’ được gọi là nghịch đảo của a sao cho a  a’ = a’  a = e 63
61. Nhóm giao hoán Commutative group .Còn được gọi làabelian group .Là1 group mà toán tử của nhóm thỏa mãn thêm thuộc nh commutativity. ◦Commutativity: a,b G thì a  b = b  a .G = có phải là nhóm giao hoán (commutative group) không? Yes 64
62. Finite Group/Subgroup .Group được gọi là hữu hạn (finite) nếu số phần tử của nó là hữu hạn. .Subgroup: tập con H của group G được gọi là subgroup của G nếu chính H cũng là1 group với cùng phép toán của G. ◦Ví dụ: H = có phải là subgroup của G= ? Không. Vì tuy H là subset của G nhưng phép toán của H là cộng modulo 10, phép toán của G là cộng modulo 12 65
63. Cyclic subgroup .Nhóm con vòng (cyclic subgroup) : làsubgroup của 1 group được tạo ra từ phép power của 1 phần tử nào đó ◦Power có nghĩa là lặp lại nhiều lần phép toán của nhóm. 66
64. Example 4.7 Four cyclic subgroups can be made from the group G = . They are H1 = , H2 = , H3 = , and H4= G. H1 H3 H4 H2 H2 4.67
65. Ví dụ .Ba cyclic subgroup từ group G= .G chỉ có 4 phần tử là1,3,7,9 10 mod 10 = 1 H1 70 mod 10 = 1 71 mod 10 = 7 H3 30 mod 10 = 1 72 mod 10 = 9 3 1 7 mod 10 = 3 3 mod 10 = 3 H3 32 mod 10 = 9 90 mod 10 = 7 3 3 mod 10 = 7 91 mod 10 = 9 H2 68
66. Cyclic group .Nhóm vòng (cyclic group) làgroup mà chính nó cũng làcyclic subgroup. ◦Ví dụ H4=G G là 1 cyclic group. .Phần tử tạo ra cyclic group được gọi làgenerator. 69
67. Ví dụ .The group G = is a cyclic group with two generators, g = 1 and g = 5. .The group G = is a cyclic group with two generators, g = 3 and g = 7. 70
68. Bậc của nhóm (Order of the Group) .Bậc của 1 nhóm hữu hạn |G| là số phần tử trong nhóm G. .Bậc của G= là (n) .Ví dụ: bậc của nhóm G = ? ◦ |G| =  (21) =  (3) ×  (7) = 2 × 6 =12. ◦ Z21* ={1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20} 71
69. Bậc của phần tử Order of an Element .Bậc của phần tử a, ký hiệu ord(a) trong nhóm G là số nguyên nhỏ nhất i sao cho ai  e (mod n) với e là phần tử đồng nhất .Bậc của phần tử làgenerator cũng là bậc của nhóm vòng mà nó tạo ra. 72
70. Ví dụ1 .Tìm bậc của tất cả các phần tử trong G= . .Nhóm có (10) = 4 phần tử, Z10∗={1,3,7,9}. Bậc của mỗi phần tử được nh bằng cách trial and error a. 11 ≡ 1 mod (10) → ord(1) = 1. b. 34 ≡ 1 mod (10) → ord(3) = 4. c. 74 ≡ 1 mod (10) → ord(7) = 4. d. 92 ≡ 1 mod (10) → ord(9) = 2. 9.73
71. Primitive root .Trong nhóm G = , khi bậc của 1 phần tử bằng với (n), thì phần tử này được gọi là primitive root của nhóm. 74
72. * Primitive root của Z19 là 2,3,10,13,14,15 75
73. Ví dụ: tìm primitive của 76
74. Nhóm vòng Cyclic Group .Nếu g là primitive root trong nhóm thì g có thể tạo (generate) tập Zn* như sau: 1 2 3 (n) Zn∗ = {g , g , g , , g } 77
75. Ring .Ring R= có2 phép toán ◦Phép toán thứ nhất  thỏa mãn cả5 thuộc nh của nhóm giao hoán (abelian group) ◦Phép toán  chỉ cần thỏa mãn 2 thuộc nh đầu nhưng phải có nh phân phối (distributivity) đối với phép toán thứ nhất   a,b,c R a (b c) = (a b) (a c) .Commutative ring là ring mà phép toán thứ hai thỏa mãn cả thuộc nh giao hoán (commutative) 78
76. Ring R = là commutative ring?? 79
77. Field .Field F= là1 commutative ring mà phép toán thứhai thỏa mãn cả5 thuộc nh nhưng phần tử identity của phép toán thứ nhất không có nghịch đảo đối với phép toán thứhai 80
78. Field 81
79. Finite field .Finite field hay còn gọi làGalois field là1 field mà số phần tử của nó làp n với p là số nguyên tố (prime) và n là1 số nguyên dương Note Một Galois field, GF(pn), là một trường hữu hạn có pn phần tử. 83
80. GF(p) field .Khi n = 1 thìGF(p) 84
81. CÁC BÀI TOÁN KHÓ GIẢI PHẦN V 87
82. . Phân tích thừa số nguyên tố . Thặng dư bậc hai . Logarithm rời rạc 88
83. Định lý số học cơ bản Fundamental Theorem of Arithmetic .Bất kỳsố dương nào lớn hơn 1 đều cóthể biể u diễn duy nhất dưới dạng thừa số nguyên tố (prime factorization) ◦Với p1, p2, , pk là các số nguyên tố ◦e1, e2, , ek là các số nguyên dương 89
84. Thặng dư bậc hai Quadratic Residuosity ∗ .Phần tử x∈ Zn là thặng dư bậc hai modulo n (quadratic ∗ residue modulo n) nếu tồn tại 1 phần tử y ∈ Zn sao cho x =y2 (mod n ) . Phần tử y được gọi là căn bậc hai của x modulo n (square root of x modulo n). ∗ .Thặng dư bậc hai trong Zn được ký hiệun QR 90
85. Phân loại .Xét 2 trường hợp thặng dư bậc hai modulo n với: ◦N là số nguyên tố ◦N là hợp số bài toán thặng dư bậc hai (Quadratic residuosity problem QRP) 91
86. Thặng dư bậc hai modulolà sốnguyên tố Quadratic Residuosity modulo prime ∗ .Mỗi phần tử trong Zn hoặc là thặng dư bậc hai (quadratic residue ) hoặc không thặng dư bậc hai (quadratic nonresidue) ∗ ◦Tập hợp tất cả số không thặng dư bậc hai trong Zn là phần bù (complement) của QRn, ký hiệu QNRn ∗ QNRn = Zn \ QRn 92
87. Ví dụ thặng dư bậc hai modulo prime ∗ .Trong Z7 các phần tử {1, 2, 3, 4, 5, 6} có thể lũy thừa bậc hai như sau: .Chỉ có 1,4,2 trong hàng thứ hai, nó chính là các thặng dư bậc hai QR7 = {1, 2, 4} ∗ QNR7 = Z 7 \ QR7 = {3, 5, 6} 93
88. Ví dụ thặng dư bậc hai modulolà sốnguyên tố .Tìm QR19 và QNR19? x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 x2 1 4 9 16 6 17 11 7 5 5 7 11 17 6 16 9 4 1 94
89. Thặng dư bậc hai với modulo là số nguyên tố .Với 1 số nguyên tố lẻ p>2, luôn có ∗ .Với mọi số nguyên tố p> 2, Zp được phân hoạch thành 2 nhóm con có kích cỡ bằng nhau QRp và QNRp (mỗi nhóm con chứa (p− 1)/2 phần tử) 95
90. Tiêu chuẩn Euler Euler’s criterion ∗ .Cho p là 1 số nguyên tố. Đối với bất kỳ số x∈ Zp ,x ∈ QRp nếu và chỉ nếu .Nếu tiêu chuẩn Euler không thỏa mãn thì .Tiêu chuẩn Euler dùng để xác định xem 1 số x có thuộc QRp hay không? 96
91. Ví dụ QR7 = {1, 2, 4} ∗ QNR7 = Z 7 \ QR7 = {3, 5, 6} .Với x=2 QR7 thì p-1 x 2 23 mod 7 1 .Với x = 5 QNR7 thì p-1 x 2 53 mod 7 -1 97
92. Bài toán thặng dư bậc hai (Quadratic residuosity problem QRP) ∗ .Cho n là một hợp số nguyên dương n∈ N và x ∈ Zn . Bài toán QRP sẽ quyết định x có thuộc QRn hay không?? .Hiện vẫn chưa có giải thuật hiệu quả nếu đầu vàolà1 số n ∗ ∈ N (tích của 2 số nguyên tố lớn) và x ∈ Zn có thể xác định được x có là thặng dư bậc hai modulo n hay không? 98
93. Bài toán thặng dư bậc hai (Quadratic residuosity problem QRP) .Đã được chỉ rằng có thể tính được căn bậc hai củax nếu và chỉ nếu phân tích được thừa số của n. ∗ Tính căn bậc hai trongZ n cũngkhó tương đương với bài toán phân tích số n. 99
94. Exponentiation vàlogarithm 9.100
95. Lũy thừa modulo Modular Exponentiation .Tính ab (mod n)?? .Giải thuật đơn giản nhất là nhân a (mod n ) b lần .Giả sử b = 23 .Có cách nào ngắn hơn không??? 101
96. Lũy thừa modulo Modular Exponentiation .Chỉ cần 7 lần nhân 102
97. Fast exponential algorithm Square-and-multiply algorithm .Sử dụng khai triển nhị phân của số mũ b để biến đổi phép tính ab thành 1 chuỗi các phép bình phương và nhân. 103
98. The square-and-multiply algorithm .Tính 722 (mod 11) ◦Tính b = (22)10 = (10110)2 . ◦Áp dụng giải thuật trên để tính như sau: 104
99. Discrete logarithm function ∗ .P là 1 số nguyên tố (prime) và g là primitive root của Zp . Hàm gọi là hàm discrete exponentiation của cơ số g. .Vì Exp là song ánh nên hàm ngược của nó là: Được gọi là hàm discrete logarithm 105
100. Discrete Logarithm Problem (DLP) .Cho g là 1 primitive root của Zp* và h là 1 phần tử khác 0 của Zp. Bài toán Discrete Logarithm là bài toán m số mũ (exponent) x sao cho .Số x được gọi làdiscrete logarithm của h cơ sốg và được ký hiệu logg(h). 106
101. Discrete Logarithm Problem (DLP) .Nếu m được 1 số mũ nguyên x sao cho gx =h thì sẽ cóvô số lời giải vì theo định lý Fermat Nếu x là lời giải của gx =h thìx + k(p − 1) cũng là lời giải với mọi giá trị k vì 107
102. Ví dụ .Cho số nguyên tố p = 56509, và g=2 là1 primitive root của Zp*. Làm thế nào để nh discrete logarithm của h = 38679? .Lần lượt nh: .Cho đến khi m thấy kết quả bằng với 38679. Việc nh toán này khó thực hiện bằng tay, nhưng nếu dùng máy nh thì dễ dàng nh được logp(h) = 11235. 108
103. Đặc điểm của Discrete logarithm .Discrete logarithm khác nhiều so với continuous logarithm được dùng trong số thực hay phức. ◦Về mặt thuật ngữ thì như nhau, cảhai loại logarithm đều là nghịch đảo của lũy thừa (exponentiation) ◦Nhưng lũy thừa modulo p thì khác xa với lũy thừa thông thường. Kết quả của lũy thừa modulo p thay đổi bất thường không theo quy luật như lũy thừa thông thường 109
104. Continous logarithm 110
105. Note The discrete logarithm problem has the same complexity as the factorization problem. 112
106. Định lý sốdư Trung hoa (Chinese Remainder Theorem) x ≡ a1 (mod n1) x ≡ a2 (mod n2) x ≡ ak (mod nk) . Là hệ thống gồm k phương trình đồng dư với n1, ,nk . Các giá trị1 n , , nk từng đôi một nguyên tố cùng nhau. . Hệ thống có một nghiệm duy nhất x thuộc Zn GV Phi Loan - BM HTTT - Khoa CNTT - HUI 113
107. Giải thuật tìm số dư Trung Hoa Chinese remainder algorithm (CRA) .Đặt mi = n/ni với i =1, ,k, −1 và yi = m i (mod ni) Khi đó nghiệm x được nh như sau: GV Phi Loan - BM HTTT - Khoa CNTT - HUI 114
108. Ví dụ .Cho 1 hệ3 phương trình đồng dư sau: x ≡ 5(mod7) x ≡ 3 (mod 11) x ≡ 11 (mod 13) Hãy m nghiệm x GV PHI LOAN - BM HTTT - KHOA CNTT - HUI 115
109. Ví dụ . n1 =7, n2 =11, n3 =13 tất cả các cặp đều nguyên tố cùng nhau . a1 =5, a2 =3 vàa 3 =11 . Tính n =7 · 11 · 13 = 1001 Tính m1 = 1001/7 = 143 m2 = 1001/11 = 91 m3 = 1001/13 = 77 GV Phi Loan - BM HTTT - Khoa CNTT - HUI 116
110. Ví dụ −1 .Tính y1 ≡ 143 (mod 7) = 5 −1 y2 ≡ 91 (mod 11) = 4 −1 y3 ≡ 77 (mod 13) = 12 Tính x = a1m1y1 + a2m2y2 +a3m3y3 = 5x143x5 + 3x91x4 + 11x77x12 x = 14831 GV Phi Loan - BM HTTT - Khoa CNTT - HUI 117
111. Hệ2 phương trình đồng dư .Xét hệ 2 phương trình: x ≡ a1 (mod n1) x ≡ a2 (mod n2) với gcd(n1,n2)=1 Tính Khi đó: u  (a2 – a1)t (mod n2) Giải thuật này ứng dụng rất nhiều trong hệ mật mã RSA 1 GV PHI LOAN - BM HTTT - KHOA CNTT - HUI 118