Bài giảng Mật mã hóa hiện đại - Chương 2: Cơ sở toán học - Phạm Việt Hà

Nội dung text: Bài giảng Mật mã hóa hiện đại - Chương 2: Cơ sở toán học - Phạm Việt Hà

1. TT CNTT HN Wednesday, April 25, 2012 MẬT MÃ HÓA HIỆN ĐẠI Chương 2: Cơ sở toán học TS. Phạm Việt Hà VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.1.Một số kiếnthứctoánhọc . Cấutrúcđạisố . Số học modulo VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 2 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 1
2. TT CNTT HN Wednesday, April 25, 2012 2.2. Cấutrúcđạisố . Cấutrúcđạisố: • Định nghĩa nhóm. TậphợpG đóvới phép toán . đã cho đượcgọilànhóm, nếunóthỏa mãn các tính chấtsauvớimọiphầntử a, b, c thuộcG: – Tính kếthợp (a.b).c = a.(b.c) – Có đơn vị e: e.a = a.e = a – Có nghịch đảo a-1: a.a-1 = e – Nếu có thêm tính giao hoán a.b = b.a, thì gọi là nhóm Aben hay nhóm giao hoán. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 3 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.2. Cấutrúcđạisố • Định nghĩa nhóm xyclic. – Định nghĩalũythừanhư là việcápdụng lặp phép toán: Ví dụ: a3 = a.a.a – Và đơnvị e=a0 – Một nhóm đượcgọi là xyclic nếumọiphầntửđềulàlũy thừacủamộtphầntử cốđịnh nào đó. Chẳng hạnb = ak đốivớia cốđịnh và mỗi b trong nhóm. Khi đóa được gọilàphầntử sinh của nhóm. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 4 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 2
3. TT CNTT HN Wednesday, April 25, 2012 2.2. Cấutrúcđạisố • Vành: Cho mộttập R các “số” với hai phép toán đượcgọilàcộng và nhân. Ở đây “số” đượchiểulàphầntử củatậphợp và hai phép toán trên xác định trên tậphợp đó. Tậpvới hai phép toán trên đượcgọilàvành, nếu hai phép toán thoả mãn các tính chấtsau: – Với phép cộng, R là nhóm Aben – Với phép nhân, có: – tính đóng và – tính kếthợp – tính phân phối đốivới phép cộng a(b+c) = ab + ac – Nếu phép nhân có tính giao hoán thì tạo thành vành giao hoán. – Nếu phép nhân có nghịch đảo và không có thương 0 (tức là không có hai phần khác 0 mà tích của chúng lạibằng 0), thì nó tạo thành miền nguyên VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 5 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.2. Cấutrúcđạisố • Trường là mộttậphợpF với hai phép toán cộng và nhân, thoả mãn tính chấtsau: – Với phép cộng F là nhóm Aben – Với phép nhân F trừ phầntử 0 là nhóm Aben. – F là mộtvành Có thể nói là có các phép toán cộng, trừ, nhân, chia số khác 0. Phép trừđượccoi như là cộng vớisốđốicủa phép cộng và phép chia là nhân vớisốđốicủa phép nhân: a– b = a + (-b) a / b = a.b-1 • Ví dụ: Dễ dàng thấy, với phép cộng và nhân thông thường: – Tậpsố nguyên Z là nhóm Aben với phép cộng – Tậpsố nguyên Z là vành giao hoán. – Tậpsố hữutỉ Q là trường. – Tậpsố thực R là trường. – Tậpsố phức C là trường với phép cộng và nhân hai số phức. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 6 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 3
4. TT CNTT HN Wednesday, April 25, 2012 2.3. Số học Modulo • Cho số tự nhiên n và số nguyên a. Ta định nghĩa: a mod n là phầndư dương khi chia a cho n. • Định nghĩa quan hệ tương đương trên tậpsố nguyên a ≡ b mod n khi và chỉ khi a và b có phầndư như nhau khi chia cho n. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 7 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ – 2.3. Số học Modulo • Ví dụ: 100 mod 11 = 1; 34 mod 11 = 1, nên 100 ≡ 34 mod 11 • Số b đượcgọilàđạidiệncủaa, nếua ≡ b mod n (a = qn + b) và 0 <= b < n. • Ví dụ: -12 mod 7 ≡ -5 mod 7 ≡ 2 mod 7 ≡ 9 mod 7. Ở đây 2 là đạidiện của –12, -5, 2 và 9. • Trong Modulo 7 ta có các lớptuơng đương viết trên các hàng như sau: – Các phầntử cùng cột là có quan hệđồng dư với nhau. – Tậpcácđạidiệncủacácsố nguyên theo Modulo n gồmn phầntử ký hiệunhư sau: Zn = { 0, 1, 2, 3, , n-1 }. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 8 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 4
5. TT CNTT HN Wednesday, April 25, 2012 2.3. Số học Modulo Ướcsố • Số b không âm đượcgọilàướcsố củaa, nếucósố m sao cho: a = mb trong đóa, b, m đều nguyên. • Tức là a chia hết cho b, ký hiệulà b|a • Ví dụ: 1, 2, 3, 4, 6, 8, 12, 24 là các ướcsố của24 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 9 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.3 Các phép toán số học trên Modulo • Cho trướcmộtsố n. Ta muốnthựchiện các phép toán theo Modulo của n. Ta có thể thựchiệncácphéptoántrêncácsố nguyên như các phép cộng, nhân các số nguyên thông thường sau đórútgọnlạibằng phép lấy Modulo hoặccũng có thể vừa tính toán, kếthợpvớirútgọntạibấtcứ thời điểmnào: (a+b) mod n = [a mod n + b mod n] mod n (*) (a.b) mod n = [a mod n . b mod n] mod n ( ) • Như vậy khi thực hiện các phép toán ta có thể thay các số bằng các số tương đương theo Modulo n đó hoặc đơn giản hơn có thể thực hiện các phép toán trên các đại diện của nó: Zn = { 0, 1, 2, 3, , n-1 }. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 10 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 5
6. TT CNTT HN Wednesday, April 25, 2012 2.3 Các phép toán số học trên Modulo • Zn với các phép toán theo Modulo tạo thành vành giao hoán có đơn vị. Các tính chất kết hợp, giao hoán và nghịch đảo được suy ra từ các tính chất tương ứng của các số nguyên. • Các chú ý về tính chất rút gọn: – Nếu (a+b)≡(a+c) mod n, thì b≡c mod n – Nhưng (ab)≡(ac) mod n, thì b≡c mod n chỉ khi nếu a là nguyên tố cùng nhau với n • Ví dụ: Tính (11*19 + 1017) mod 7 = ? VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 11 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.3 Các phép toán số học trên Modulo . Ví dụ: bảng modulo 8 với phép cộng VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 12 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 6
7. TT CNTT HN Wednesday, April 25, 2012 2.3 Các phép toán số học trên Modulo . Ước số chung lớn nhất. • Bài toán: Cho hai số nguyên dương a và b. Bài toán tìm ước chung lớn nhất của hai số nguyên dương là bài toán chung của lý thuyết số. Ta ký hiệu GCD(a,b) là ước số chung dương lớn nhất của a và b, tức là số nguyên dương vừa là ước của a vừa là ước của b và là số nguyên dương lớn nhất có tính chất đó. • Ví dụ: GCD(60,24) = 12 ; GCD (6, 15) = 3; GCD(8, 21) = 1. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 13 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.3 Các phép toán số học trên Modulo . Nguyên tố cùng nhau: Ta thấy 1 bao giờ cũng là ước số chung của hai số nguyên dương bất kỳ. Nếu GCD(a, b) = 1, thì a, b đựơc gọi là hai số nguyên tố cùng nhau: • Ví dụ: GCD(8,15) = 1, tức là 8 và 15 là hai số nguyên tố cùng nhau VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 14 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 7
8. TT CNTT HN Wednesday, April 25, 2012 2.3 Các phép toán số học trên Modulo . Tìm ước chung lớn nhất. Bây giờ chúng ta xét bài toán tìm ước số chung lớn nhất của hai số nguyên dương cho trước. Dễ dàng chứng minh được tính chấtsau: GCD(a,b) = GCD(b, a mod b) . Như vậy để tìm ướcsố chung củamộtcặpsố cho trước, ta đưavề bài toán tìm ước chung củacặpsố gồmsố nhỏ hơn trong hai sốđóvàphầndư củasố lớn khi chia cho số nhỏ hơn. ThuậttoánƠcơlít tạo nên vòng lặp, ở mỗibước ta áp dụng tính chấttrênchođến khi phầndưđó còn khác 0. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 15 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.3 Các phép toán số học trên Modulo . Thuật toán Ơcơlit tìm GCD(a, b) A=a, B=b while B>0 R = A mod B A = B, B = R return A VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 16 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 8
9. TT CNTT HN Wednesday, April 25, 2012 2.3 Các phép toán số học trên Modulo . Ví dụ: GCD(1970,1066) 1970 = 1 x 1066 + 904 gcd(1066, 904) 1066 = 1 x 904 + 162 gcd(904, 162) 904 = 5 x 162 + 94 gcd(162, 94) 162 = 1 x 94 + 68 gcd(94, 68) 94 = 1 x 68 + 26 gcd(68, 26) 68 = 2 x 26 + 16 gcd(26, 16) 26 = 1 x 16 + 10 gcd(16, 10) 16 = 1 x 10 + 6 gcd(10, 6) 10 = 1 x 6 + 4 gcd(6, 4) 6 = 1 x 4 + 2 gcd(4, 2) 4 = 2 x 2 + 0 gcd(1970, 1066) = 2 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 17 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.3 Các phép toán số học trên Modulo . Trường Galoa • Ta muốn đi tìm một trường số có hữu hạn các phần tử, tức là một tập hữu hạn các phần tử mà ở đó có thể cộng trừ, nhân, chia mà không vượt ra ngoài phạm vi tập hữu hạn các phần tử đó. Trường Galoa thuộc lọai đó và đóng vai trò quan trọng trong lý thuyết mã. • Có thể chứng minh được rằng số các phần tử của trường hữu hạn bất kỳ bằng lũy thừa của pm của sô nguyên tố p nào đó, ta ký hiệu trường Galoa đó là GL(pm). Thông thường ta sử dụng các trường: GL(p) và GL(2m).Sau đây chúng ta sẽ xây dựng các trường Galoa đó. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 18 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 9
10. TT CNTT HN Wednesday, April 25, 2012 2.3 Các phép toán số học trên Modulo . Trường Galoa GL(p), vớip làsố nguyên tố. • GL(p) gồmtập {0,1, , p-1}. • Với các phép toán cộng và nhân Modulo, như ta đãbiếtGL(p) tạo thành một vành giao hoán. Vì p là số nguyên tố nên mọisố khác 0 nhỏ hơnp đều nguyên tố cùng nhau vớip. • GL(p) tạo thành trường vì mọia thuộc {1, , p-1} đềucóphầntử nghịch đảoa-1: a . a-1 = 1. Thựcvậy vì a và p nguyên tố cùng nhau nên theo thuật toán tìm nghịch đảodưới đây ta sẽ tìm được nghịch đảocủaa. • Như vậy trên GL(p) ta có thể thựchiện các phép toán cộng, trừ, nhân, chia. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 19 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.4 Số học đathức . Số học đa thức • Ta xét tập các đa thức Pn có bậc nhỏ hơn hoặc bằng n: n i n n-1 a x f(x) = anx + an-1x + + a1x + a0 =  i i 0 • Trên tập các đa thức đó ta có thể có một số cách khác nhau thực hiện các phép toán cộng và nhân đa thức VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 20 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 10
11. TT CNTT HN Wednesday, April 25, 2012 2.4 Số học đathức • Phép toán đa thức thông thường – Cộng trừ các hệ số tương ứng – Nhân mọi hệ số với cùng một số. – Ví dụ: f(x) = x3 + x2 + 2 và g(x) = x2 – x + 1 f(x) + g(x) = x3 + 2x2 – x + 3 f(x) – g(x) = x3 + x + 1 f(x) . g(x) = x5 + 3x2 –2x + 2 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 21 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.4 Số học đathức • Phép toán đa thức với Modulo hệ số – Cho số nguyên tố p tùy ý – Tính các hệ số theo Modulo p. Khi đótập các hệ sốđượclấytừ trường GL(p). Còn phép nhân đathứccóthể nhận đượckếtquả là đa thứcbậclớnhơnn. – Ta thường quan tâm đến Mod 2, tứclàmọihệ số là 0 hoặc1 – Ví dụ: f(x) = x3 + x2 và g(x) = x2 + x + 1 f(x) + g(x) = x3 + x + 1 f(x) . g(x) = x5 + x2 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 22 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 11
12. TT CNTT HN Wednesday, April 25, 2012 2.4 Số học đathức . Phép toán đathứcvới Modulo đathức • Cho đathức g(x) bậc n và các hệ số của các đathức xét trong mục này lầy trong trường Galoa GF(p) vớip làsố nguyên tố. Viết đathức f(x) dướidạng: f(x) = q(x) g(x) + r(x) trong đó r(x) là phầndư khi chia f(x) cho g(x). Rõ ràng bậccủa r(x) sẽ nhỏ hơnbậccủa g(x).Ta viết: r(x) = f(x) mod g(x) VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 23 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.4 Số học đathức . Nếu không có phần dư, tức là r(x) = 0, ta nói g(x) là ước của f(x) hay g(x) chia hết f(x) hay f(x) chia hết cho g(x). . Trong trường hợp g(x) không có ước ngoài 1 và chính nó, thì ta nói g(x) là đa thức nguyên tố hoặc không rút gọn được. Ví dụ g(x) = x3 + x + 1 là đa thức nguyên tố. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 24 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 12
13. TT CNTT HN Wednesday, April 25, 2012 2.4 Số học đathức 3 2 2 . Ví dụ: Trong GF(2 ) ta có (x +1) tương ứng dãy bít 1012 và (x +x+1) tương ứng với dãy 1112 . Tổng hai đathứctrênlà • (x2+1) + (x2+x+1) = x • 101 XOR 111 = 0102 . Tích củahaiđathứclà • (x+1).(x2+1) = x.(x2+1) + 1.(x2+1) = x3+x+x2+1 = x3+x2+x+1 • 011.101 = (101)<<1 XOR (101)<<0 = 1010 XOR 101 = 11112 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 25 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.4 Số học đathức Phép rút gọn theo Modulo là: • (x3+x2+x+1 ) mod (x3+x+1) = (x3+x2+x+1 ) - (x3+x+1 ) = x2 • 1111 mod 1011 = 1111 XOR 1011 = 01002 . Như vậy trường Galoa GL(2n) bao gồm 2n phần tử. Muốn trường Galoa có số phần tử lớn tuỳ ý, ta chỉ việc tăng và lấy n thích hợp. . Đặc biệt việc tính toán các phép toán cộng trừ, nhân, chia trên đó rất nhanh và hiệu quả trên các thao tác của các thiết bị phần cứng trường Galoa đóng vai trò quan trọng trong lý thuyết mã VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 26 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 13
14. TT CNTT HN Wednesday, April 25, 2012 2.5 Số nguyên tố • Các số nguyên tố – Như chúng ta đã biết số nguyên tố là các số nguyên dương chỉ có ước số là 1 và chính nó. Chúng không thể được viết dưới dạng tích của các số khác. – Các số nguyên tố là trung tâm của lý thuyết số. Số các số nguyên tố là vô hạn. – Ví dụ: Danh sách các số nguyên tố nhỏ hơn 200: 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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 27 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.5 Số nguyên tố . Một trong những bài toán cơ bản của số học là phân tích ra thừa số nguyên tố số a, tức là viết nó dưới dạng tích của các số nguyên tố. . Lưu ý rằng phân tích là bài toán khó hơn rất nhiều so với bài toán nhân các số để nhận được tích. . Ta có kết luận: mọi số nguyên dương đều có phân tích duy nhất thành tích các lũy thừa của các số nguyên tố • Ví dụ: 51=3x17; 3600=24×32×52 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 28 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 14
15. TT CNTT HN Wednesday, April 25, 2012 2.5 Số nguyên tố . Các số nguyên tố cùng nhau và GCD • Hai số nguyên dương a và b không có ước chung nào ngoài 1, được gọi là nguyên tố cùng nhau. – Ví dụ: 8 và 15 là nguyên tố cùng nhau, vì ước của 8 là 1, 2, 4, 8, còn ước của 15 là 1, 3, 5, 15. Chỉ có 1 là ước chung của 8 và 15. • Ngược lại có thể xác định ước chung lớn nhất bằng cách trong các phân tích ra thừa số của chúng, tìm các thừa số nguyên tố chung và lấy bậc lũy thừa nhỏ nhất trong hai phân tích của hai số đó. – Ví dụ. Ta có phân tích: 300=22 ×31 ×52 và 18=21×32. Vậy GCD(18,300)=21×31×50=6 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 29 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.6 Định lý Ferma . Định lý Ferma (Định lý Ferma nhỏ) ap-1 mod p = 1 trong đó p là số nguyên tố và a là số nguyên bất kỳ khác bội của p: GCD(a, p) = 1. • Hay với mọi số nguyên tố p và số nguyên a không là bội của p, ta luôn có ap = a mod p • Công thức trên luôn đúng, nếu p là số nguyên tố, còn a là số nguyên dương nhỏ hơn p. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 30 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 15
16. TT CNTT HN Wednesday, April 25, 2012 2.6 Định lý Ferma . Ví dụ: Vì 5 và 7 là các số nguyên tố. 2 và 3 không là bội tương ứng của 7 và 5, nên theo định lý Ferma ta có: 27-1 mod 7 = 1 (= 26 mod 7 = 64 mod 7= 1) 35-1 mod 5 = 1 (= 34 mod 5 = 81 mod 5= 1) . Kết quả trên được dùng trong khoá công khai. Nó cũng được sử dụng để kiểm tra tính nguyên tố của một số nguyên p nào đó. (?) VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 31 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.7 Định lý Ole . Hàm Ole • Cho n là một số nguyên dương. Khi thực hiện phép tính đồng dư n của mọi số nguyên khác ta nhận được tập đầy đủ các phần dư có thể có là: 0, 1, 2, , n-1 • Từ tập trên ta tìm tập rút gọn (n) bao gồm các số nguyên tố cùng nhau với n và quan tâm đến số lượng các phần tử như vậy đối với số nguyên dương n cho trước. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 32 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 16
17. TT CNTT HN Wednesday, April 25, 2012 2.7 Định lý Ole . Các tính chấtcủahàm(n): • Dễ dàng thấy, nếup làsố nguyên tốФ(p) = p-1 • Nếu (m, n) = 1, thì: Ф(m.n) = Ф(m).Ф(n) e1 ek • Nếun = p1 pk là phân tích ra thừasố nguyên tố của n thì: 1 1 1 (n) n 1 1 1 p1 p2 pk VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 33 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.7 Định lý Ole . Ví dụ: • Tính (37); (25); (18); (21)? (37) = 37 – 1 = 36 (25) = (52) = 20 (18) = (2). (9) = 1. (32) = 6 (21) = (3). (7) = 2.6 = 12 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 34 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 17
18. TT CNTT HN Wednesday, April 25, 2012 2.7 Định lý Ole . Định lý Ole: Định lý Ole là tổng quát hoá của Định lý Ferma a(n) mod n= 1 vớimọicặpsố nguyên dương nguyên tố cùng nhau a và n: gcd(a,n)=1. • Ví dụ: – a = 3; n = 10; Ф(10)=4; Vì vậy 34 = 81 = 1 mod 10 – a = 2; n =11; Ф(11)=10; Do đó 210 = 1024 = 1 mod 11 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 35 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.8 Kiểmtrasố nguyên tố . Kiểm tra tính nguyên tố • Giả sử cần phải tìm một số nguyên tố rất lớn. Lấy ngẫu nhiên một số đủ lớn, ta cần phải kiểm tra xem số đó có phải là số nguyên tố không? – Cách 1: Thử bằng phép chia – Cách 2: sử dụng các phép kiểm tra tính nguyên tố thống kê dựa trên các tính chất: – Mà mọi số nguyên tố phải thỏa mãn – Nhưng có một số số không nguyên tố, gọi là giả nguyên tố cũng thoả mãn tính chất đó VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 36 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 18
19. TT CNTT HN Wednesday, April 25, 2012 2.8 Kiểmtrasố nguyên tố . Cụ thể là phép kiểm tra dựa trên Định lý Ferma như sau: • Nếu số n cần kiểm tra tính nguyên tố là số nguyên tố, thì nó sẽ thoã mãn định lý Ferma đối với mọi số a nhỏ hơn nó an-1 mod n = 1. • Như vậy, lấy ngẫu nhiên số a và kiểm tra xem nó có tính chất trên không. Nếu có thì n có thể là số nguyên tố, nếu cần độ tin cậy lớn hơn, thì ta kiểm tra liên tiếp nhiều lần như vậy với các số ngẫu nhiên a được chọn. Sau mỗi lần qua được phép thử, xác suất để n là số nguyên tố lại tăng lên VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 37 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.8 Kiểmtrasố nguyên tố . Chú ý rằng: • nếu bi mod n = 1, thì: b2i mod n = (1)2 mod n = 1 và • nếu bi mod n = n – 1, thì: b2i mod n = (n - 1)2 mod n = (n2 – 2n +1) mod n = 1 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 38 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 19
20. TT CNTT HN Wednesday, April 25, 2012 2.8 Kiểmtrasố nguyên tố . Phân bố nguyên tố. • Định lý về số nguyên tố khẳng định số nguyên tố xuấthiện trung bình sau mỗi khoảng lnn số nguyên (nếu xét các số trong kích thướcn). • Lưuý đây chỉ là trung bình, vì có lúc các số nguyên rấtgần nhau và có lúc lạirất xa nhau. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 39 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.8 Kiểmtrasố nguyên tố . Trong nhiềutrường hợpta muốn tìm cách để tăng tốc độ tính toán Modulo. Các phép toán trên modulo các số nhỏ tính nhanh nhiềuso với các số lớn. . Chính vì vậynếusố lớn phân tích được thành tích của các số nhỏ, từng cặp nguyên tố cùng nhau, thì ta sẽ có cách tính hiệuquả nhờ vào định lý Phầndư Trung hoa VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 40 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 20
21. TT CNTT HN Wednesday, April 25, 2012 2.9 Định lý phầndư Trung Hoa n1, , nk nguyên tố cùng nhau từng đôi mộtthìhệ sau có nghiệm duy nhất theo modulo n = n1 nk x  a 1 mod n 1 x  a 2 mod n 2 x  a k mod n k VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 41 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.9 Định lý phầndư Trung Hoa . Có thể triển khai Định lý Trung Hoa theo một số cách như sau: • 1. Tính toán theo modulo số lớn: – Để tính A mod M, với M (M= m1m2 mk) khá lớn và A là biểu thức số học nào đó. Trước hết ta cần tính tất cả ai = A mod mi. Sau đósử dụng công thức: k A  a i c i mod M i 1 Trong đó: Mi = M/mi 1 ci M i M i mod mi ; 1 i k – Áp dụng tính ví dụ: 178 mod 77? VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 42 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 21
22. TT CNTT HN Wednesday, April 25, 2012 2.9 Định lý phầndư Trung Hoa 18 . Áp dụng định lý phần dư Trung hoa, ta coi A = 17 , m 1 = 7, m2 = 11. Khi đó M1 = 11, M2 = 7 và -1 -1 • 11 mod 7 = 4 mod 7 = 2, suy ra c1 = 11*2 = 22; -1 • 7 mod 11 = 8, suy ra c2 = 7*8 = 56; 8 8 8 2 4 • 17 mod 7 = (17 mod 7) mod 7 = 3 mod 7 = (3 ) mod 7 = a1 = 2; • 178 mod 11 = (17 mod 11)8 mod 11 = 68 mod 11 2 4 4 = (6 ) mod 11 = 3 mod 11 = a2 = 4; . Vậy 178 mod 77 = (2*22 + 4*56) mod 77 = 268 mod 77 = 37 mod 77 = A = 37; VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 43 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.9 Định lý phầndư Trung Hoa Giải hệ phương trình modulo: – Cho x = ai mod mi,với GCD(mi, mj) = 1, với mọi i khác j. Khi đó ta cũng áp dụng Định lý phần dư Trung Hoa để tìm x. – Áp dụng tính ví dụ: – Tìm x với: VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 44 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 22
23. TT CNTT HN Wednesday, April 25, 2012 2.9 Định lý phầndư Trung Hoa . Áp dụng định lý phần dư Trung hoa, ta tính: • 7-1 mod 11 = 8 và 11-1 mod 7 = 2. Như vậy: • x = (5*2*11 + 6*8*7) mod (7*11) = 61 mod 77. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 45 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2. Một số kiến thức toán học  Định lí: nếu(n1, n2) = 1 thì x  a mod n1 , x  a mod n 2 có nghiệm duy nhất x  a mod( n 1 .n 2 ) VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 46 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 23
24. TT CNTT HN Wednesday, April 25, 2012 2.9 Định lý phầndư Trung Hoa . Căn nguyên tố • Từ Định lý Ole ta có a(n)mod n=1, với a và n là nguyên tố cùng nhau. Nếu không có số mũ dương nào nhỏ hơn Ф(n), mà có tính chất như vậy đối với a, thì khi đó ta gọi a là căn nguyên tố của n. • Ví dụ: – (a) Xét xem a = 2 có phảilàcăn nguyên tố của 5 không? – (b) a = 3 có là căn nguyên tố của 8 không? VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 47 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2. Một số kiến thức toán học . (a) Ta có: • 2 mod 5 = 2; 22mod 5 = 4; 23mod 5 = 3; 24mod 5 = 1. • Rõ ràng m= 4= Ф(5) là số mũ dương nhỏ nhất có tính chất 2m mod 5 = 1, nên 2 là căn nguyên tố của 5. . (b) Ta có: • 3 mod 8 = 3; 32 mod 8 = 1; 33mod 8 = 3; 34 mod 8 = 1 • Rõ ràng m= 2 < 4 = Ф(8) là số mũ dương nhỏ nhất có tính chất 3m mod 8 = 1, nên 3 không là căn nguyên tố của 8. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 48 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 24
25. TT CNTT HN Wednesday, April 25, 2012 2.10 Logarit rờirạc • Bài toán ngược của bài toán lũy thừa là tìm logarit rời rạc của một sô modulo p, tức là tìm số nguyên x sao cho: ax = b mod p. Hay còn được viết là x=logab mod p • Nếu a là căn nguyên tố của p và p là số nguyên tố, thì luôn luôn tồn tại logarit rời rạc, ngược lại thì có thể không • Ví dụ: – Tìm x = log2 3 mod 13? – Tìm x = log3 4 mod 13? VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 49 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 2.10 Logarit rờirạc x . Tìm x = log2 3 mod 13? (Hay: 2 = 3 mod 13) • 20 mod 13 = 1; • 21 mod 13 = 2, • 22 mod 13 = 4, • 23 mod 13 = 8, • 24 mod 13 = 3. • Vậy log2 3 mod 13 = 4. x . Tìm x = log3 4 mod 13? (Hay 3 = 4 mod 13) • Trong trường hợp này không có lời giải, vì • 30 mod 13 = 1; • 31 mod 13 = 3; • 32 mod 13 = 9; • 33 mod 13 = 1= 30 mod 13 VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 50 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 25
26. TT CNTT HN Wednesday, April 25, 2012 2.10 Logarit rờirạc . Ta nhận thấy, trong khi bài toán lũy thừa là dễ dàng, thì bài toán logarit rời rạc là rất khó. Đây cũng là một cơ sở của mã công khai VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 51 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ CCIT/RIPT 26