›
›

Bài giảng Giải thuật nâng cao - Một số giải thuật tren số

pdf 57 trang hapham 50
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Giải thuật nâng cao - Một số giải thuật tren số", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_giai_thuat_nang_cao_mot_so_giai_thuat_tren_so.pdf

Nội dung text: Bài giảng Giải thuật nâng cao - Một số giải thuật tren số

  1. MỘT SỐ GIẢI THUẬT TRÊN SỐ TS. NGÔ QUỐC VIỆT 2016
  2. Nội dung 1. Giới thiệu 2. Phép chia và số học modular 3. Bài toán đồng dư và ứng dụng 4. Số nguyên tố Giải thuật nâng cao-Một số giải thuật trên số
  3. Giới thiệu • Lý thuyết số khảo sát số nguyên, các tính chất và các ứng dụng liên quan. • Khảo sát: một số ký hiệu, thuật ngữ, định lý liên quan • Lý thuyết số ứng dụng trong nhiều giải thuật quan trọng: hàm băm, mã hóa, chữ ký số, online security. Giải thuật nâng cao-Một số giải thuật trên số
  4. Phép chia • Cho a, b là số nguyên, ≠ 0. Nói a chia hết b nếu tồn tại số nguyên c sao cho: = . • • Ký hiệu chia hết: | . Ví dụ : 3 | 12 • Ký hiệu không chia hết: ∤ (ví dụ: 5 ∤ 12) • Định lý: a,b,c Z: 1. | 2. ( |  | ) | ( + ) 3. | | 4. ( |  | ) | • Bổ đề: nếu | , | thì | + 푛 , , , , , 푛 ∈ 푍. Giải thuật nâng cao-Một số giải thuật trên số
  5. Giải thuật “Chia” • Định lý: cho a, d là số nguyên dương, thì tồn tại duy nhất q và r, 0 ≤ < , sao cho = 푞 + . • q: thương số; a: số bị chia; d: số chia; r: số dư • Cho số dương a và d dương, để xác định r, lặp lại trừ d với a, cho tới khi còn lại r mà nhỏ hơn d • Cho a âm và d dương, để xác định r, lặp lại cộng d với a, cho tới khi còn lại r, là dương (hoặc zero) nhỏ hơn d Giải thuật nâng cao-Một số giải thuật trên số
  6. Biểu diễn số nguyên • Cho > 1 nguyên dương. Có thể biểu diễn số nguyên dương n duy nhất theo dạng −1 푛 = + −1 + ⋯ + 1 + 0, ∈ , 0, , < , ≠ 0 Ví dụ: = 859 = 8. 102 + 5101 + 9 = 4 2 1 (10110)2 = 12 + 12 + 12 = (22)10 = 3 2 0 (3 0퐹)16 = 316 + 1016 + 1516 = (14863)10 Giải thuật nâng cao-Một số giải thuật trên số
  7. Số học modular • Cho a là số nguyên, m số nguyên dương. Ký hiệu 표 biểu diễn phần dư khi a được chia cho m. • Ví dụ: 9 표 4 = 1 −13 표 4 = 3 • Cho a, b là số nguyên, m số nguyên dương. Khi đó “a đồng dư b modulo m” nếu: | − . Ký hiệu: ≡ ( 표 ). • Ký hiệu: ≢ ( 표 ), a không đồng dư b mod m. • Chú ý: số dư luôn dương. Giải thuật nâng cao-Một số giải thuật trên số
  8. Số học modular • Định lý: Cho a, b là số nguyên, m số nguyên dương. Thì ≡ ( 표 ) nếu và chỉ nếu 표 = 표 . • Định lý: Cho m là số nguyên dương. Hai số nguyên a, b là đồng dư modulo m nếu và chỉ nếu tồn tại số k sao cho: = + . • Ví dụ: = + ∗ 6 hoặc = − ∗ 6. (17 ≡ 5 ( 표 2)) • Định lý: Cho m là số nguyên dương. Nếu ≡ ( 표 ) và ≡ ( 표 ) thì: ( + ) ≡ ( + ) ( 표 ) và ≡ ( 표 ). • Bổ đề: Cho a, b là số nguyên, m số nguyên dương thì + 표 = 표 + 표 표 và 표 = 표 . ( 표 ) 표 Giải thuật nâng cao-Một số giải thuật trên số
  9. Số học modular • Ví dụ: Các lớp đồng dư modulo 5. ≡ 0 (mod 5) 20 -1 15 ≡ 1 10 (mod 5) ≡ 4 19 5 21 14 16 (mod 5) 9 11 4 0 6 1 3 2 8 7 13 12 18 17 ≡ 3 22 ≡ 2 (mod 5) (mod 5) -7 • Hỏi: xác định vị trí của -1 và -7? Giải thuật nâng cao-Một số giải thuật trên số
  10. Số học modular • Đặt: 푍 = 푖 ∈ | 푖 < = 0, 1, , − 1 . • Ký hiệu + : cộng các số trong Zm. + = + 표 • Ký hiệu . : nhân các số trong Zm . = . 표 • Các phép toán + và . được gọi là cộng và nhân modulo. 7 +11 9 = 7 + 9 표 11 = 5 7.11 9 = 7.9 표 11 = 8 • Các phép + và . thỏa mãn các tính chất: đóng, kết hợp, giao hoán, phân bố, phần tử đơn vị. • 푍 là nhóm giao hoán, và 푍 cùng với hai phép + , . là vành giao hoán Giải thuật nâng cao-Một số giải thuật trên số
  11. Ứng dụng của đồng dư modulo • Hàm băm (xem lại bảng băm – cấu trúc dữ liệu) • Số giả ngẫu nhiên • Kiểm tra chữ số (digit checks) • Mã hóa Giải thuật nâng cao-Một số giải thuật trên số
  12. Số giả ngẫu nhiên • Cần mô phỏng trên máy tính để tạo ra số ngẫu nhiên số giả ngẫu nhiên (P.288-Rosen’s book) • Phương pháp đồng dư tuyến tính: giải thuật phổ biến để sinh số ngẫu nhiên • Chọn 4 số nguyên • Tâm (seed) x0: giá trị khởi đầu 0 ≤ 0 < • Modulus m • Bội số a: 2 ≤ < • Gia số c: 0 ≤ < • Sinh dãy số ngẫu nhiên, * 푛 | 0 ≤ 푛 < +, theo biểu thức: 푛+1 = ( 푛 + ) 표 Giải thuật nâng cao-Một số giải thuật trên số
  13. Số giả ngẫu nhiên • Công thức: xn+1 = (axn + c) mod m • Ví dụ: Cho x0 = 3, m = 9, a = 7, and c = 4 x1 = 7x0+4 = 7*3+4 = 25 mod 9 = 7 x2 = 7x1+4 = 7*7+4 = 53 mod 9 = 8 x3 = 7x2+4 = 7*8+4 = 60 mod 9 = 6 x4 = 7x3+4 = 7*6+4 = 46 mod 9 = 1 x5 = 7x4+4 = 7*1+4 = 11 mod 9 = 2 x6 = 7x5+4 = 7*2+4 = 18 mod 9 = 0 x7 = 7x6+4 = 7*0+4 = 4 mod 9 = 4 x8 = 7x7+4 = 7*4+4 = 32 mod 9 = 5 • Các giá trị = 232 − 1, = 75 = 16,807, = 0 thường được dùng để sinh số ngẫu nhiên • Yêu cầu: anh/chị hãy viết hàm sinh ra số ngẫu nhiên Giải thuật nâng cao-Một số giải thuật trên số
  14. The Caesar cipher • Julius Caesar sử dụng thủ tục sau để mã hóa messages • Hàm f để mã hóa chữ được định nghĩa như sau: f(p) = (p+3) mod 26 • Với p là a letter (0 là A, 1 là B, 25 là Z, etc.) • Giải mã: f-1(p) = (p-3) mod 26 • Thủ tục này được gọi là substitution cipher Giải thuật nâng cao-Một số giải thuật trên số
  15. Mã hóa Caesar • Mã hóa “go cavaliers” • Chuyển thành số: g = 6, o = 14, etc. • Chuỗi số: 6, 14, 2, 0, 21, 0, 11, 8, 4, 17, 18 • Áp dụng cipher cho từng số: f(6) = 9, f(14) = 17, etc. • Chuỗi đã mã: 9, 17, 5, 3, 24, 3, 14, 11, 7, 20, 21 • Chuyển số thành chuỗi: 9 = j, 17 = r, etc. • Chuỗi chữ: jr wfdydolhuv • Giải mã “jr wfdydolhuv” • Chuyển thành số: j = 9, r = 17, etc. • Chuỗi số: 9, 17, 5, 3, 24, 3, 14, 11, 7, 20, 21 • Áp dụng cipher cho từng số : f-1(9) = 6, f-1(17) = 14, etc. • Chuỗi số đã giải mã: 6, 14, 2, 0, 21, 0, 11, 8, 4, 17, 18 • Chuyển số thành chuỗi: 6 = g, 14 = 0, etc. • Chuỗi gốc: “go cavaliers” Giải thuật nâng cao-Một số giải thuật trên số
  16. Số nguyên tố và ước chung lớn nhất • Số nguyên dương p được gọi là số nguyên tố nếu chỉ chia hết cho chính nó và 1. Ngược lại gọi là số hợp nguyên (composite integer). • Chú ý: 1 không phải là số nguyên tố Giải thuật nâng cao-Một số giải thuật trên số
  17. Số nguyên tố và ước chung lớn nhất • Định lý số học cơ bản: mọi số nguyên đều có thể biểu diễn duy nhất bởi tích của các số nguyên tố. • Định lý: số hợp nguyên n có số chia nguyên tố nhỏ hơn hoặc bằng 풏. • Suy ra: n là số nguyên tố nếu không chia hết cho bất kỳ số nguyên tố nào nhỏ hơn hay bằng 푛. • Định nghĩa: hai số nguyên a, b là nguyên tố cùng nhau nếu ước chung lớn nhất (GCD) của chúng là 1. • Định nghĩa: Các số 1, 2, , 푛 là đôi một nguyên tố cùng nhau nếu: 푖, 푗 = 1, 1 ≤ 푖 < 푗 ≤ 푛 Giải thuật nâng cao-Một số giải thuật trên số
  18. Một số định lý • Định lý Bézout : • ∀ , 푖푛푡푒 푒 푠, , > 0: ∃푠, 푡: gcd , = 푠 + 푡 • Bổ đề 1: • ∀ , , > 0: gcd , = 1 푛 | thì | . • Bổ đề 2: • Nếu p là số nguyên tố và | 1 2 푛 thì ∃푖: | 푖 • Định lý 2: • Nếu ≡ ( 표 ) và gcd , = 1 thì ≡ ( 표 ) Giải thuật nâng cao-Một số giải thuật trên số
  19. Chứng minh định lý Bézout Định lý Bézout:  ≥ ≥ 0 푠, 푡: gcd ( , ) = 푠 + 푡 Chứng minh Bổ đề Bézout là hệ quả của Euclidean division. = 1 + 1, 0 = b 2. Take reminder r of a/b 3. Set a := b, b := r so that a >= b 4. Repeat until b = 0 Giải thuật nâng cao-Một số giải thuật trên số
  20. Chứng minh định lý Bézout = 1 + 1, 0 < 1 < , gcd , = gcd ( , ) = 1 2 + 2, 0 < 2 < 1 ⋮ 푛−1 = 푛 푛+1 + 푛+1, 0 < 푛+1 < 푛, 푛 = 푛+1 푛+2 • 푛+1 là phần dư khác zero cuối cùng trong tiến trình trên. 푛+1 là linear combination của 푛 và 푛−1, 푛 là linear combination của 푛−1 và 푛−2, • ⋯ • 푛+1 là linear combination của a và b và là gcd của chúng. Giải thuật nâng cao-Một số giải thuật trên số
  21. Ví dụ về định lý Bézout gcd(252,198) = 18. Biểu diễn 18 là kết hợp tuyến tính của 252 và 198. Sử dụng divisions theo Euclid Algorithm: gcd(252,198) = gcd(198,54) = 252 = 1 198 + 54 (252 mod 198 = 54) gcd(54,36) = 198 = 3 54 + 36 (198 mod 54 = 36) gcd(36,18) = 54 = 1 36 +18 etc. gcd(18,0) = 18 36 = 2 18 Vì, 18 = 54 - 1 36 (3rd equation) 36 = 198 – 3 54 (2th equation) Do đó 18 = 54 - 1 (198 – 3 54) = 4 54 – 1 198 Nhưng 54 = 252 - 1 198; thay thế 54 trong biểu thức này : 18 = 4 (252 - 1 198) - 1 198 = 4 252 – 5 198 Giải thuật nâng cao-Một số giải thuật trên số
  22. Chứng minh Bổ đề 1 Bổ đề 1: ∀ , , > 0: gcd , = 1 & | thì | . Theo định lý Bézout: 푠, 푡: 푠 + 푡 = 1. Nhân hai vế với c, c푠 + 푡 = . Nếu | thì | 푡 . Ngoài ra | 푠 nên | c푠 + 푡 . Vì vậy: | 푠 + 푡 ⇒ | Giải thuật nâng cao-Một số giải thuật trên số
  23. Chứng minh bổ đề 2 Bổ đề 2: Nếu p là số nguyên tố và | 1 2 푛 thì ∃푖: | 푖 Chứng minh quy nạp: n = 1, hiển nhiên Giả sử đúng với 푛 < . Giả sử | 1 2 . Đặt = 1 2 −1 Trường hợp 1: nếu | , ∃푖: | 푖 Trường hợp 2: nếu ≦ | ⇒ gcd , = 1. Ngoài ra | (giả thiết). Theo bổ đề 1 thì: |  Giải thuật nâng cao-Một số giải thuật trên số
  24. Chứng minh định lý 2 Định lý 2: Nếu ≡ ( 표 ) và gcd , = 1 thì ≡ ( 표 ) Do: ≡ ( 표 ) nên: − ⟹ ( − ) Theo bổ đề 1 với: gcd , = 1 và | ( − ) nên | ( − ) Vì vậy: ≡ ( 표 )  Giải thuật nâng cao-Một số giải thuật trên số
  25. Ứng dụng của định lý 2 • Trong phát sinh số giả ngẫu nhiên: chọn bội số a là nguyên tố cùng nhau với m. Nghĩa là: gcd ( , ) = 1. Thì: • Hàm chuyển từ xn thành xn+1 là đơn ánh ′ • Vì nếu: 푛+1 ≡ 푛 표 = 푛 표 , (giả sử gia số ′ = 0), thì: 푛 ≡ 푛( 표 ) • Nghĩa là: dãy số giả ngẫu nhiên không lặp lại cho đến khi gặp lại số x0 ban đầu Giải thuật nâng cao-Một số giải thuật trên số
  26. Lũy thừa modulo • Cho m nguyên dương, giá trị của 푛 표 được gọi là lũy thừa modulo. • Không thực tế nếu tính = 푛, sau đó tính 표 • Dựa trên khai triển nhị phân của số nguyên để tính 푛 풌− 풌− 풌− 풏 = 풌− + 풌− +⋯+ + = 풌− • Để tính 푛 표 thì cần tính: 2 3 −1 2 표 , 2 표 , 2 표 , , 2 표 (bổ đề: 표 = 표 . ( 표 ) 표 ) Giải thuật nâng cao-Một số giải thuật trên số
  27. Giải thuật tính lũy thừa modulo • Bổđề: 표 = 표 . ( 표 ) 표 Giải thuật nâng cao-Một số giải thuật trên số
  28. Giải thuật tính lũy thừa modulo: ví dụ • Tính 3644 표 645 Giải thuật nâng cao-Một số giải thuật trên số
  29. Số Mersenne • Số có dạng: 2푛 − 1 • Số nguyên tố Mersenne: là số nguyên tố có dạng 2 − 1, với p nguyên tố. • Ví dụ: 25-1 = 31 là nguyên tố Mersenne, nhưng 211-1 = 2047 không phải là nguyên tố Mersenne • Nếu M là nguyên tố Mersenne thì M(M+1)/2 là số hoàn hảo (số bằng với tổng các thương của nó – ví dụ: 28 = 1 + 2 + 4 + 7 + 14 ) • Ví dụ: 25-1 = 31 là nguyên tố Mersenne, thì 31*32/2=496 là số hoàn hảo • 496 = 2*2*2*2*31 1+2+4+8+16+31+62+124+248 = 496 • Số nguyên tố lớn nhất xác định được là số Mersenne. Giải thuật nâng cao-Một số giải thuật trên số
  30. Số nguyên tố Mersenne • Định lý: có vô hạn số nguyên tố • Kiểm tra Lucas-Lehmer: xác định số nguyên tố Mersenne • Số nguyên tố lớn nhất được tìm thấy: 12 triệu chữ số (tháng 10/2014) Giải thuật nâng cao-Một số giải thuật trên số
  31. Định lý số nguyên tố • Tỉ lệ của số lượng các số nguyên tố không lớn hơn x và x/ln(x) tiến tới 1 khi x tăng vô hạn • Số lượng các số nguyên tố nhỏ hơn x xấp xỉ bằng x/ln(x) (in 1792 by Gauss at 15 ) • Cơ hội để số x là số nguyên tố xấp xỉ bằng: 1/ln(x). • Ví dụ: xét số nguyên tố có 200 chữ số • 푙푛 10200 ≈ 460 • Trong 460 số nguyên có 200 chữ số thì có có thể có 1 số nguyên tố. • Manindra Agrawal et al (2002) giới thiệu giải thuật 푙표 푛 6 để xác định số n có phải là số nguyên tố Giải thuật nâng cao-Một số giải thuật trên số
  32. Ước chung lớn nhất • Cho hai số nguyên a, b: có thể sử dụng biểu diễn dạng tích của các nguyên tố để xác định GCD. 1 2 푛 1 2 푛 • = 1 2 푛 , = 1 2 푛 . Các số mũ là nguyên không âm min ( 1, 1) min ( 2, 2) min ( 푛, 푛) • Thì , = 1 2 푛 • Ví dụ: 120 = 23. 3.5, 500 = 22. 53 . Khi đó: 120,500 = 2min (3,2)3min (1,0)5min (1,3) = 20 • Nhận xét: biểu diễn dạng thừa số nguyên tố có thể xác định được bội chung nhỏ nhất Giải thuật nâng cao-Một số giải thuật trên số
  33. Bội chung nhỏ nhất 1 2 푛 1 2 푛 • Cho = 1 2 푛 , = 1 2 푛 . Các số mũ là nguyên không âm, thì: max ( 1, 1) max ( 2, 2) max ( 푛, 푛) • 푙 , = 1 2 푛 • Ví dụ: 95256 = 23. 35. 72; 432 = 24. 33. Khi đó: 푙 95256,432 = 2max (3,4)3max (5,3)7max (2,0) = 190512 Giải thuật nâng cao-Một số giải thuật trên số
  34. Định lý LCM & GCD • Định lý: cho a, b là hai số nguyên dương, thì × = ( , ) × 푙 , • Ví dụ: : (10,25) = 5, 푙 (10,25) = 50, vì vậy 10 × 25 = 5 × 50 • Định lý: cho = 푞 + , với a, b, q, r là số nguyên. Thì ( , ) = ( , ). Giải thuật nâng cao-Một số giải thuật trên số
  35. Giải thuật Euclid xác định GCD • Tính GCD dựa trên phân tích thừa số nguyên tố: hạn chế vì cần xác định các thừa số nguyên tố • Nhận xét: Với mọi cặp số nguyên a, b thì: ( , ) = 표 , procedure procedure (a,b:positive integers) x := a y := b while y 0 begin r := x mod y x := y y := r end { gcd(a, b) is x } Giải thuật nâng cao-Một số giải thuật trên số
  36. Giải thuật Euclid-Ví dụ gcd(372,164) = gcd(164, 372 mod 164). 372 mod 164 = 372 164 372/164 = 372 164·2 = 372 328 = 44. gcd(164,44) = gcd(44, 164 mod 44). 164 mod 44 = 164 44 164/44 = 164 44·3 = 164 132 = 32. gcd(44,32) = gcd(32, 44 mod 32) = gcd(32,12) = gcd(12, 32 mod 12) = gcd(12,8) = gcd(8, 12 mod 8) = gcd(8,4) = gcd(4, 8 mod 4) = gcd(4,0) = 4. Giải thuật nâng cao-Một số giải thuật trên số
  37. Đồng dư tuyến tính-nghịch đảo • Đồng dư tuyến tính có dạng: ≡ ( 표 ). Mục tiêu là tìm x thỏa biểu thức trên • Gọi a’ là nghịch đảo (modulo m)của a, nếu: ′ ≡ 1 ( 표 ) • Nếu tồn tại a’, biểu thức trên: ′ ≡ ′ ( 표 ) 1. ≡ ′ ( 표 ) Định lý: nếu gcd ( , ) = 1 và > 1 thì tồn tại duy nhất a’ là nghịch đảo (modulo m) của a. Giải thuật nâng cao-Một số giải thuật trên số
  38. Ví dụ: đồng dư tuyến tính-nghịch đảo • Tìm nghịch đảo của 4 (modulo 9) 4,9 = 1 9 = 2 4 + 1 1 = −2 4 + 1 9 − 4 ≡ 1 ( 표 9) Các số đồng dư tuyến tính với -2 (mod 9) đều là nghịch đảo của 4 (modulo 9) Giải thuật nâng cao-Một số giải thuật trên số
  39. Định lý phần dư Trung hoa • Định lý: cho 1, , 푛 > 1 là nguyên tố cùng nhau, và 1, , 푛 là các số nguyên bất kỳ . Thì hệ phương trình ≡ 표 , 푖 = 1 → 푛 có lời giải duy nhất modulo 푖 푖 = 1 · ⋯ · 푛. Nghĩa là 0 ≤ < , và nếu có y thỏa hệ phương trình trên thì ≡ ( 표 ). Đặt: 푖 = / 푖 thì gcd 푖, 푖 = 1 ⇒ ∃! 푖: 푖 푖 ≡ 1 ( 표 푖) (định lý về đồng dư nghịch đảo) Đặt 풙 = 풊 풊풚풊푴풊. Vì: 푖| , ≠ 푖, nên ≡ 0 ( 표 푖) Nên: 표 푖 = 푙 푙 푙 푙 표 푖 = 푖 푖 푖 표 푖 = 푖 표 푖 Vậy: ≡ 푖 표 푖, ∀푖 = 1 → 푛. Và x là lời giải cần tìm. Giải thuật nâng cao-Một số giải thuật trên số
  40. Định lý phần dư Trung hoa-ví dụ Tìm x sao cho: ≡ 2 ( 표 3), ≡ 3 ( 표 7), m = m1· ·mn. ≡ 2 ( 표 7) Dựa trên định lý phần dư Trung hoa M = m/m m = 3 5 7 = 105 i i a1 = 2, a2 = 3, a3 = 2 yi Mi ≡ 1 (mod mi). m1 = 3, m2 = 5, m3 = 7 M1 = m/3 = 105/3 = 35 x = ∑i ai yi Mi 2 là nghịch đảo của M1 = 35 (mod 3) (vì 35x2 ≡ 1 (mod 3)) M2 = m/5 = 105/5 = 21 1 là nghịch đảo của M2 = 21 (mod 5) (vì 21x1 ≡ 1 (mod 5)) M3 = m/7 = 15 1 là nghịch đảo của M3 = 15 (mod 7) (vì 15x1 ≡ 1 (mod 7)) Vậy , x ≡ 2 2 35 + 3 1 21 + 2 1 15 = 233 ≡ 23 (mod 105) Lời giải: x ≡ 23 (mod 105) Giải thuật nâng cao-Một số giải thuật trên số
  41. Định lý phần dư Trung hoa-MATLAB function x=CRT(r,p) if (length(r)==length(p)) l=length(r); CM=1; for i=1:l CM=CM*p(i); end M=zeros(1,l); for i=1:l M(i)=CM/p(i); end IM=zeros(1,l); x=0; for i=1:l IM(i)=invmodan(M(i),p(i)); x=x+r(i)*M(i)*IM(i); end display('Value of x: '); x=mod(x,CM); else display('Length of r and p matrices must be same'); end Giải thuật nâng cao-Một số giải thuật trên số
  42. Định lý phần dư Trung hoa-MATLAB function y=invmodn(x,p) n=eulerphi(p); % Compute Euler's totient function of p b=dec2bin(n-1); len=length(b); a=ones(1,len); a(1)=rem(x,p); for i=1:(len-1) a(i+1)=rem((a(i))^2,p); end b=fliplr(b); mul=1; for i=1:len if b(i)=='0' a(i)=1; end mul=mul*a(i); mul=rem(mul,p); end y=rem(mul,p); Giải thuật nâng cao-Một số giải thuật trên số
  43. Định lý phần dư Trung hoa-MATLAB function phi=eulerphi(n) if (n>1 && mod(n,1)==0) f=factor(n); l=length(f); phi=1; for i=1:l phi=phi*(f(i)-1); end elseif (n==1) phi=1; else display('Invalid number entered'); end Giải thuật nâng cao-Một số giải thuật trên số
  44. Tính toán số nguyên lớn • Cho số nguyên a bất kỳ, 0 ≤ < , với = 푖 , gcd 푖, 푗≠푖 = 1 thì a có thể được biểu diễn bởi các phần dư của a với mi. Nghĩa là bộ n 표 1, 표 2, , 표 푛 . • Xét hệ phương trình: ≡ 표 , với = 표 . Thì tồn 푖 푖 푖 푖 tại duy nhất nghiệm x. • Xét: = 표 , thì x là nghiệm của hệ phương trình trên. Giải thuật nâng cao-Một số giải thuật trên số
  45. Tính toán số nguyên lớn Hãy biểu diễn số nguyên x nhỏ hơn 12 bởi một cặp. Chọn cặp là hai số nguyên tố cùng nhau. Ví dụ 3 và 4. Biểu diễn x theo các bộ ( 표 3, 표 4). Xác định phần dư của các số chia cho 3 và 4. 0=(0,0); 1=(1,1); 2=(2,2); 3=(0,3); 4=(1,0); 5=(2,1); 6=(0,2); 7=(1,3); 8=(2,0); 9= (0,1); 10 = (1,2); 11= (2,3) • Ví dụ: 11 = (11 mod 3, 11 mod 4) = (2, 3) Vậy: có thể sử dụng hai số nguyên nhỏ để biểu diễn số nguyên nhỏ hơn 12. Giải thuật nâng cao-Một số giải thuật trên số
  46. Tính toán số nguyên lớn • Để thực hiện tính toán trên số nguyên lớn, thực hiện theo các bước sau • Thực hiện trên các phép toán trên các phần dư! • Có thể thực hiện song song. • Hay thực hiện tuần tự trên máy đơn. • Tiếp tục đến khi desired result < m. Giải thuật nâng cao-Một số giải thuật trên số
  47. Tính toán số nguyên lớn Ví dụ: giả sử có thể tính toán dễ với các số nhỏ hơn 100; Khi đó có thể giới hạn tính toán các số nguyên thành tính các số nhỏ hơn 100, nếu có thể biểu diễn ở dạng phần dư đôi một nguyên tố cùng nhau, ví dụ: 99, 98, 97, 95. Theo định lý phần dư Trung Hoa, mọi số nhỏ hơn 99 98 97 95 = 89.403.930 có thể biểu diễn duy nhất theo các phần dư của chúng với các số 99, 98 , 97 , 95. Ví dụ, số 123684 có thể biểu diễn bởi (123684 mod 99; 123684 mod 98; 123684 mod 97; 123684 mod 95) = (33,8,9,89) 413456 có thể biểu diễn bởi (413456 mod 99; 413456 mod 98; 413456 mod 97; 413456 mod 95)= (32,92,42,16) Giải thuật nâng cao-Một số giải thuật trên số
  48. Tính toán số nguyên lớn Để cộng hai số 123.684, và 413456. (33, 8, 9, 89)+(32, 92 , 42, 16) = (65 mod 99, 100 mod 98, 51 mod 97, 105 mod 95) = (65, 2, 51, 10) Để tìm tổng: giải hệ phương trình đồng dư tuyến tính sau x ≡ 65 (mod 99) x ≡ 2 (mod 98) x ≡ 51 (mod 97) x ≡ 10 (mod 95) Lời giải: x= 537,140 Giải thuật nâng cao-Một số giải thuật trên số
  49. Tính toán số nguyên lớn • Ví dụ, các số sau là nguyên tố cùng nhau: 25 m1 = 2 −1 = 33,554,431 = 31 · 601 · 1,801 27 m2 = 2 −1 = 134,217,727 = 7 · 73 · 262,657 28 m3 = 2 −1 = 268,435,455 = 3 · 5 · 29 · 43 · 113 · 127 29 m4 = 2 −1 = 536,870,911 = 233 · 1,103 · 2,089 31 m5 = 2 −1 = 2,147,483,647 (prime) • Vậy, có thể biểu diễn số nguyên lớn 42 139.5 • m = ∏mi ≈ 1.4×10 ≈ 2 theo các phần dư ri modulo với các mi trên. 30 • Vd:. 10 = (r1 = 20900945; r2 = 18304,504; r3 = 65829085; r4 = 516865185; r5 = 1234980730) • Để cộng hai số theo biểu diễn đồng dư • Cộng các phần dư tương ứng. • Lấy kết quả mod 2k−1: • Nếu ≥ giá trị 2k−1, trừ nó với 2k−1 • Chú ý: No carries are needed between the different pieces! Giải thuật nâng cao-Một số giải thuật trên số
  50. Pseudoprimes • Nếu n nguyên tố thì 2푛−1 ≡ 1 ( 표 푛), tuy nhiên điều ngược lại không đúng [nghĩa là nếu 2푛−1 ≡ 1 ( 표 푛) thì n có thể không nguyên tố]. • Ví dụ: 2 ퟒ −1 ≡ 1 ( 표 341) , nhưng 341 = 11 × 31 không phải là số nguyên tố. • Số n với tính chất này được gọi là pseudoprime. • Tổng quát, nếu 풏− ≡ ( 풐풅 풏) và n là số hợp nguyên, thì n được gọi là pseudoprime cơ số b. Giải thuật nâng cao-Một số giải thuật trên số
  51. Định lý nhỏ của Fermat • Định lý: (Fermat’s Little Theorem.) • Nếu p nguyên tố và a nguyên không chia hết p; ( ∤ ), thì −1 ≡ 1 ( 표 ) • Ngoài ra, với mọi số nguyên a thì ≡ ( 표 ) −1 • Nhận xét: nếu ∈ 푍 thì ≡ 1 trong Zp. Giải thuật nâng cao-Một số giải thuật trên số
  52. Các số Carmichael • Định nghĩa: số hợp nguyên n thỏa mãn 푛−1 ≡ 1 표 푛 , ∀ : gcd , 푛 = 1 được gọi là số Carmichael. • Ví dụ: 561 là số Carmichael • 561=3.11.17 • Nếu gcd ( , 561) = 1 thì gcd ( , 3) = 1, gcd ( , 11) = 1, gcd ( , 17) = 1 • 2 ≡ 1 표 3 ; 1 ≡ 1 표 11 ; 16 ≡ 1 표 17 ; • 560 = 2 280 ≡ 1 ( 표 3) • 560 = 10 56 ≡ 1 ( 표 11) • 560 = 16 35 ≡ 1 ( 표 16) • Các số: 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341 là số Carmichael Giải thuật nâng cao-Một số giải thuật trên số
  53. Mã RSA Phát sinh mã 1. Chọn hai prime numbers p và q (ngẫu nhiên). 2. 푛 = 푞, dùng làm modulus. 3. 휑(푛) = 휑( )휑(푞) = ( − 1)(푞 − 1) = 푛 − ( + 푞 − 1) hàm totient), là private key 4. Chọn số e sao cho 1 < 푒 < 휑(푛), và gcd(e, φ(n)) = 1. • e là public key exponent. • Giá trị e nhỏ không hiệu quả để bảo mật. 5. Tìm: d ≡ e−1 (mod φ(n)). • d là private key exponent • Public key: số n và e. • Private key: số d. Giải thuật nâng cao-Một số giải thuật trên số
  54. Mã RSA Mã hóa 1. A gởi 푛, 푒 (public key - gởi đi) cho B. A giữ bí mật giá trị d. 2. B cần gởi gói tin M mã với 푛, 푒 để gởi cho A. 3. Chuyển M thành giá trị nguyên m. 4. Tính ≡ 푒 표 푛 , là gói B gởi cho A. Giải mã • A cần phục hồi m, M khi nhận được c từ B. • ≡ 표 푛 Giải thuật nâng cao-Một số giải thuật trên số
  55. Mã RSA-ví dụ • Cho = 61, 푞 = 5. • 푛 = 61 ∗ 53 = 3233 • 휑 3233 = 3120 • Chọn 1 < 푒 < 3120 nguyên tố cùng nhau với 3120. Chọn e = 17. • 푒 × = 1 ( 표 3120) d = 2753. • Public key: 푛 = 3233, 3 = 17 • Private key: = 2753. • Cho m = 65 • Mã hóa m: = 6517 표 3233 = 2790. • Giải mã c: = 27902753 표 3233 = 65. Giải thuật nâng cao-Một số giải thuật trên số
  56. Bài tập 2006 1. Tìm nghiệm: 2 2 표 3 2006 2005 22205 2 2 = 2 2.2 = 4 ≡1 ( 표 3) 2. Chứng minh: nếu tồn tại số đảo (multiplicative inverse hoặc reciprocal) modulo N, thì nó là duy nhất. Giả sử tồn tại hai số đảo x1, x2 khác nhau của a. 1 = 1. 1 = 풙 . . 2 = 1. 2 = 2 표 Giải thuật nâng cao-Một số giải thuật trên số
  57. Bài tập 3. Xét RSA, p=7, q=11. Tìm e và d. − 1 ∗ 푞 − 1 = 60 Tìm e nguyên tố cùng nhau với 60, và có số nghịch đảo. Chọn e=11 d= 11 (mod 60). Có thể chọn các cặp (e, d) khác: (7, 43); (13, 37); (17, 53); (19, 59); (23, 47); (29, 29); (31, 31); (41, 41). 4. Cài đặt và thuyết minh RSA bằng MATLAB. Giải thuật nâng cao-Một số giải thuật trên số