›
›

Bài giảng Nhập môn Số học và thuật toán - Nguyễn Đạt Thông

pdf 54 trang ngocly 3000
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nhập môn Số học và thuật toán - Nguyễn Đạt Thông", để 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_nhap_mon_so_hoc_va_thuat_toan_nguyen_dat_thong.pdf

Nội dung text: Bài giảng Nhập môn Số học và thuật toán - Nguyễn Đạt Thông

  1. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Nhập môn SỐ HỌC THUẬT TOÁN Nguyễn Đạt Thông ndthong@math.hcmus.edu.vn Bộ môn Ứng dụng Tin học Khoa Toán - Tin học 2010 Nhập môn Số học và Thuật toán 1/54
  2. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Giới thiệu Tên học phần: Nhập môn số học thuật toán. Số tín chỉ: 4. Chuyên ngành: Phương pháp Toán trong Tin học. Học phần tiên quyết: Đại số đại cương. Học phần liên quan: Phân tích thuật toán. Lý thuyết mã hóa thông tin. Nhập môn Số học và Thuật toán 2/54
  3. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Mục tiêu Cung cấp cho sinh viên các kiến thức cơ bản của số học và thuật toán, bao gồm các định nghĩa, định lý, các bài toán cũng như các vấn đề tiêu biểu trong số học. Trình bày các ý tưởng và các cài đặt cơ bản của các thuật toán liên quan đến việc biểu diễn, tính toán, giải quyết các vấn đề của số học trên máy tính. Giới thiệu một số ứng dụng tiêu biểu của số học trong các lĩnh vực mật mã và mã hóa. Nhập môn Số học và Thuật toán 3/54
  4. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Yêu cầu Sinh viên cần tham dự các buổi học lý thuyết và thực hành, tham khảo tài liệu, làm bài tập nhóm, để có thể nắm đầy đủ nội dung chương trình. Sinh viên cần có các kỹ năng tính toán, suy luận, chứng minh, để có thể hiểu rõ và nắm vững các kiến thức nền tảng của số học. Sinh viên cần có các kỹ năng tư duy logic, lập trình, debug, để có thể cài đặt và kiểm tra các thuật toán của số học. Nhập môn Số học và Thuật toán 4/54
  5. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Nội dung lý thuyết 1 Thuật toán 2 Số nguyên 3 Các hàm số học 4 Thặng dư bình phương 5 Đường cong Elliptic 6 Một số thuật toán phân tích số nguyên 7 Một số thuật toán giải bài toán logarit rời rạc 8 Ứng dụng số học vào lý thuyết mật mã Nhập môn Số học và Thuật toán 5/54
  6. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Nội dung thực hành 1 Ngôn ngữ lập trình Python 2 Tính toán trên số nguyên 3 Các hàm số học và tính thặng dư bình phương 4 Tính toán đường cong Elliptic trên trường Zp 5 Kiểm tra số nguyên tố 6 Tìm căn theo modulo n 7 Phân tích số nguyên 8 Giải bài toán logarit rời rạc Nhập môn Số học và Thuật toán 6/54
  7. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Tài liệu tham khảo 1 Hà Huy Khoái, Phạm Huy Điển, Số học thuật toán, Hà Nội, 2002, NXB Đại học Quốc Gia Hà Nội. 2 Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 1997, CRC Press. 3 Douglas R. Stinson, Cryptography - Theory and Practice, 3rd Edition, Ontario, 1995, CRC Press. 4 David M. Burton, Elementary Number Theory, 2nd Edition, Massachusetts, 1980, Allyn and Bacon. 5 Allen Downey, ThinkPython, Massachusetts, 2008, Green Tee Press. Nhập môn Số học và Thuật toán 7/54
  8. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Tài liệu tham khảo 6 H. C. William, M. C. Wunderlich, On the Parallel Generation of the Residues for the Contrinued Fraction Factoring Algorithm, Mathematics of Computation Vol 48, 1987, American Mathematical Society. 7 Donald E. Knuth, The Art of Computer Programming, Vol. 2 - Seminumerical Algorithms, 3rd Edition, Canada, 1998, Addison Wesley. 8 T. M. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd Edition, 2001, The MIT Press. Nhập môn Số học và Thuật toán 8/54
  9. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Phương pháp đánh giá Bài tập lý thuyết và thực hành: 20% Kiểm tra giữa kỳ: 15% Thảo luận đề tài: 15% Kiểm tra cuối kỳ: 50% Nhập môn Số học và Thuật toán 9/54
  10. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Câu hỏi Q&A Nhập môn Số học và Thuật toán 10/54
  11. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Chương 1 THUẬT TOÁN Nguyễn Đạt Thông ndthong@math.hcmus.edu.vn Bộ môn Ứng dụng Tin học Khoa Toán - Tin học 2010 Chương 1: Thuật toán 11/54
  12. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Thuật toán Định nghĩa Thuật toán là một quy tắc để, với những dữ liệu ban đầu đã cho, tìm được lời giải sau một khoảng thời gian hữu hạn. Tính chất 1 Tính hữu hạn. Thuật toán cần phải kết thúc sau một số hữu hạn bước. Khi ngừng làm việc, kết quả của thuật toán phải được xác định. 2 Tính xác định. Ở mỗi bước, thuật toán cần phải xác định, nghĩa là chỉ rõ việc cần làm. Chương 1: Thuật toán 12/54
  13. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Ví dụ về thuật toán Bài toán Cho n số X[1], X[2], , X[n], tìm m và j sao cho m = X[j] = max X[k] 1≤k≤n và j lớn nhất có thể. Thuật toán 1 [Xuất phát] Đặt j ← n, k ← n − 1, m ← X[n]. 2 [Kết thúc] Nếu k = 0, kết thúc. 3 [So sánh] Nếu X[k] ≤ m, chuyển sang bước 5. 4 [Cập nhật] Đặt j ← k, m ← X[k]. 5 [Giảm k] Đặt k ← k − 1, quay lại bước 2. Chương 1: Thuật toán 13/54
  14. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Độ phức tạp của thuật toán Độ phức tạp của thuật toán được đo bằng số phép tính nhị phân phải làm khi thực hiện thuật toán. Với cùng một thuật toán, số phép tính cần thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Nói cách khác, độ phức tạp của thuật toán là một hàm số phụ thuộc độ lớn của đầu vào. Hàm số độ phức tạp của thuật toán được ước lượng trong trường hợp xấu nhất của thuật toán. Cỡ n của dữ liệu đầu vào tương đương với cỡ k = [log2 n] + 1 trên máy tính. Chương 1: Thuật toán 14/54
  15. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Bậc O-lớn Định nghĩa Giả sử f(n) và g(n) là hai hàm xác định trên tập hợp các số nguyên dương. Ta nói f(n) có bậc O-lớn của g(n), và viết f(n) = O(g(n)) hoặc f = O(g), nếu tồn tại một số C > 0 sao cho với n đủ lớn, các hàm f(n) và g(n) đều dương, đồng thời f(n) g. Tuy nhiên, ước lượng độ phức tạp của thuật toán phải là ước lượng tốt nhất có thể để tránh hiểu sai về độ phức tạp thực sự của thuật toán. Chương 1: Thuật toán 15/54
  16. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Tính chất của O-lớn Tính chất d d−1 d 1 Nếu f(n) = adn + ad−1n + + a1n + a0 thì f(n) = O(n ). 2 Nếu f1(n) = O(g(n)) và f2(n) = O(g(n)) thì f1 + f2 = O(g). 3 Nếu f1 = O(g1) và f2 = O(g2) thì f1f2 = O(g1g2). f(n) 4 Nếu tồn tại giới hạn hữu hạn lim thì f = O(g). n→∞ g(n) ε 5 Với mọi số ε > 0, log n = O(n ). Chương 1: Thuật toán 16/54
  17. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Độ phức tạp đa thức Định nghĩa Một thuật toán được gọi là có độ phức tạp đa thức, hoặc có thời gian đa thức, nếu số các phép tính cần thiết khi thực hiện thuật toán không vượt quá O(logd n), trong đó n là độ lớn của đầu vào, và d là số nguyên dương nào đó. Nếu một thuật toán có độ phức tạp đa thức và có đầu vào n là một số k-bit thì độ phức tạp của thuật toán này là O(kd), tức một đa thức của k. Các thuật toán có thời gian O(αn), với α > 1, được gọi là các thuật toán có độ phức tạp mũ, hoặc thời gian mũ. Các thuật toán có thời gian O(nd) với d > 1 là các thuật toán có độ phức tạp tương đương mũ. Chương 1: Thuật toán 17/54
  18. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Độ phức tạp dưới mũ Ngoài ra còn có những thuật toán có độ phức tạp trung gian giữa đa thức và mũ, được gọi là các thuật toán dưới mũ. Chẳng hạn, thuật toán nhanh nhất được biết hiện nay để phân tích một số nguyên n ra thừa số nguyên tố là thuật toán có độ phức tạp √ e log n log log n Với một máy tính có khả năng thực hiện 1 triệu phép tính trong 1 giây, thời gian cần thiết để chạy thuật toán này được mô tả trong bảng sau: Số chữ số thập phân Số phép tính bit Thời gian 50 1.4 × 1010 3.9 giờ 75 9.0 × 1012 104 ngày 100 2.3 × 1015 74 năm 200 1.2 × 1023 3.8 × 109 năm 300 1.5 × 1029 4.9 × 1015 năm 500 1.3 × 1039 4.2 × 1025 năm Chương 1: Thuật toán 18/54
  19. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Câu hỏi Một thuật toán cần khoảng 1027 năm để hoàn thành thì có thể xem là một thuật toán xác định không? Có 2 thuật toán phân tích thừa số nguyên tố chạy trên cùng một hệ thống máy tính. Thuật toán thứ nhất mất 3 ngày để hoàn thành, thuật toán thứ hai chạy 27 ngày vẫn chưa xong. Có thể nói thuật toán thứ nhất tốt hơn (hiệu quả hơn) thuật toán thứ hai không? Có 2 thuật toán sắp xếp dãy số chạy trên cùng một hệ thống máy tính. Để sắp xếp một dãy gồm n phần tử, thuật toán thứ nhất cần thực hiện 2n2 phép tính trong khi thuật toán thứ hai cần 50n log2 n. Có thể nói thuật toán thứ hai phức tạp hơn thuật toán thứ nhất không? Chương 1: Thuật toán 19/54
  20. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Chương 2 SỐ NGUYÊN Nguyễn Đạt Thông ndthong@math.hcmus.edu.vn Bộ môn Ứng dụng Tin học Khoa Toán - Tin học 2010 Chương 2: Số nguyên 20/54
  21. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Hệ cơ số Định lý Giả sử b là một số nguyên lớn hơn 1. Khi đó mọi số nguyên n có thể viết duy nhất dưới dạng k k−1 n = akb + ak−1b + + a1b + a0 trong đó aj là số nguyên, 0 ≤ aj ≤ b − 1, j = 0, 1, , k và hệ số đầu tiên ak 6= 0. Số b được gọi là cơ số của biểu diễn. Các hệ số aj được gọi là các chữ số. Số chữ số của n khi biểu diễn theo cơ số b là log n k = [log n] + 1 = + 1 b log b Trong cơ số tùy ý, ta có k = O(log n). Chương 2: Số nguyên 21/54
  22. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Biểu diễn và tính toán số nguyên trên máy tính Các số nguyên được biểu diễn theo cơ số nhị phân trên máy tính. Các số nguyên lớn hơn cỡ từ w của máy tính sẽ được biểu diễn theo cơ số w. Để cộng hoặc trừ hai số nguyên k-bit, ta cần O(k) phép tính bit. Để nhân hoặc chia hai số nguyên k-bit theo qui tắc thông thường, ta cần O(k2) phép tính bit. Để cải tiến tốc độ nhân hoặc chia hai số nguyên, ta có các thuật toán: Thuật toán Karatsuba - Ofman (1962). Thuật toán Sch¨onhage- Strassen (1996). Chương 2: Số nguyên 22/54
  23. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Thuật toán Karatsuba - Ofman Giả sử cần nhân hai số nguyên 2k-bit a = (a2k−1a2k−2 a1a0)2 b = (b2k−1b2k−2 b1b0)2 Ta tách các số nguyên a, b thành các số nguyên k-bit bằng cách đặt A1 = (a2k−1a2k−2 ak)2,A2 = (ak−1ak a1a0)2 B1 = (b2k−1b2k−2 bk)2,B2 = (bk−1bk b1b0)2 n n Khi đó a = 2 A1 + A0 và b = 2 B1 + B0. Kết quả của phép nhân sẽ là 2k k k k ab = (2 + 2 )A1B1 + 2 (A1 − A0)(B1 − B0) + (2 + 1)A0B0 Thuật toán có độ phức tạp O(klog2 3). Chương 2: Số nguyên 23/54
  24. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Thuật toán Sch¨onhage- Strassen Giả sử cần nhân hai số nguyên (r + 1)k-bit a = (a(r+1)k−1a(r+1)k−2 a1a0)2 b = (b(r+1)k−1b(r+1)k−2 b1b0)2 Ta tách các số nguyên a, b thành các số nguyên k-bit: rk k a = Ar2 + + A12 + A0 rk k b = Br2 + + B12 + B0 Thuật toán có độ phức tạp O(klogr+1 (2r+1)). Bằng các phương pháp tối ưu thuật toán và chọn r thích hợp, Sch¨onhage- Strassen đưa ra thuật toán có độ phức tạp O(k log k log log k). Chương 2: Số nguyên 24/54
  25. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Quan hệ đồng dư Định nghĩa Giả sử m là một số nguyên dương. Hai số a và b là đồng dư với nhau theo modulo m nếu m chia hết hiệu a − b. Ký hiệu a ≡ b mod m. Định lý (Wilson) Số p là nguyên tố khi và chỉ khi (p − 1)! ≡ −1 mod p. Định lý (Fermat bé) Nếu p là số nguyên tố và a là số không chia hết cho p thì ap−1 ≡ 1 mod p. Hệ quả. Nếu p là số nguyên tố và a là số nguyên dương thì ap ≡ a mod p. Hệ quả. Nếu p là số nguyên tố và a là số nguyên không chia hết cho p thì ap−2a ≡ 1 mod p. Chương 2: Số nguyên 25/54
  26. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Câu hỏi Số thập phân x = 2a − 5 được biểu diễn bởi 2 chữ số trong hệ cơ số a, giá trị của a là bao nhiêu? Làm thế nào để chuyển một số từ hệ cơ số a sang hệ cơ số b? Làm thế nào để chuyển một số từ hệ cơ số 2 sang hệ cơ số 16 và ngược lại? Giá trị của (11200121)3 ở hệ cơ số 9 là bao nhiêu? Nếu nhân hai số có 8 chữ số bất kỳ trong hệ cơ số 16 theo phương pháp thông thường thì cần phải thực hiện khoảng bao nhiêu phép tính bit? Giả sử x ≡ y mod ni với 1 ≤ i ≤ k, các ni nguyên tố cùng nhau đôi một. Chứng minh rằng x ≡ y mod n1n2 nk. Chương 2: Số nguyên 26/54
  27. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Số nguyên tố Định nghĩa Số nguyên tố là số nguyên lớn hơn 1, không chia hết cho số nguyên dương nào ngoài 1 và chính nó. Số nguyên lớn hơn 1 không phải là số nguyên tố thì được gọi là hợp số. Số các số nguyên tố là vô hạn. √ Mọi hợp số n đều có ước nguyên tố không vượt quá n. Bài toán đặt ra: Thuật toán kiểm tra một số nguyên n có phải là số nguyên tố hay không. Thuật toán kiểm tra một số nguyên lớn n có phải là số nguyên tố hay không. Chương 2: Số nguyên 27/54
  28. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Định lý số nguyên tố Định lý Đặt π(x) là số các số nguyên tố không vượt quá x, ta có π(x) lim = 1 x→∞ x(log x)−1 √ √ 2 n Số các số nguyên tố không vượt quá n là vào khoảng . log n Nếu chia n cho m cần O(log2 √n log2 m) phép tính bit, thì để thực  2 n  √ hiện việc kiểm tra, ta cần C log n = C n. log n 2 Để kiểm tra số n gồm 100 chữ số thập phân có phải số nguyên tố không, ta cần khoảng 1050 phép tính bit, tương đương 3.1 × 1036 năm khi thực hiện trên máy tính có khả năng tính 1 triệu phép tính mỗi giây. Chương 2: Số nguyên 28/54
  29. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Số giả nguyên tố Định nghĩa (Số nguyên tố xác suất Fermat) Giả sử b là một số nguyên dương. Nếu n là số tự nhiên và bn ≡ b mod n, thì n được gọi là số nguyên tố xác suất Fermat cơ sở b. Định nghĩa (Số giả nguyên tố Fermat) Giả sử b là một số nguyên dương. Nếu n là hợp số nguyên dương và bn ≡ b mod n, thì n được gọi là số giả nguyên tố Fermat cơ sở b. Trường hợp gcd(n, b) = 1, n là số giả nguyên tố cơ sở b khi bn−1 ≡ 1 mod n. Số 561 là một số giả nguyên tố cơ sở 2 do 561 là hợp số và 2560 ≡ 1 mod 561. Với mỗi cơ sở tùy ý, số các số giả nguyên tố là vô hạn. Chương 2: Số nguyên 29/54
  30. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Số Carmichael Định nghĩa Hợp số nguyên n thỏa mãn bn−1 ≡ 1 mod n với mọi số nguyên dương b sao cho gcd(n, b) = 1 được gọi là số Carmichael. Định lý r1 r2 rk Nếu n = q1 q2 qk , n là số Carmichael khi và chỉ khi với mọi 1 ≤ j ≤ k: (qj − 1)|(n − 1). Tồn tại vô hạn số Carmichael. Giả sử bn−1 ≡ 1 mod n. Nếu n là số nguyên tố thì b(n−1)/2 ≡ ±1 mod n. Ngược lại, n là hợp số. Số 561 là số Carmichael. Chương 2: Số nguyên 30/54
  31. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Kiểm tra Miller Định nghĩa Giả sử n là số nguyên dương lẻ, ta viết n − 1 = 2st, với s ≥ 1 và t lẻ. Ta nói n trải qua được kiểm tra Miller cơ sở b, nếu bt ≡ 1 j mod n hoặc b2 t ≡ −1 mod n với 0 ≤ j ≤ s − 1. Nếu n là số nguyên tố thì n trải qua được kiểm tra Miller với mọi cơ sở b không chia hết cho n. Nếu hợp số n trải qua được kiểm tra Miller cơ sở b thì nó được gọi là số giả nguyên tố mạnh cơ sở b. Tồn tại vô hạn số giả nguyên tố mạnh cơ sở 2. Ví dụ: Số giả nguyên tố mạnh lẻ cơ sở 2 bé nhất là 2047. Số giả nguyên tố mạnh lẻ cơ sở 2 và 3 bé nhất là 1373653. Số giả nguyên tố mạnh lẻ cơ sở 2, 3 và 5 bé nhất là 25326001. Số giả nguyên tố mạnh lẻ cơ sở 2, 3, 5 và 7 bé nhất là 3215031751. Chương 2: Số nguyên 31/54
  32. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Thuật toán Rabin - Miller Định lý Nếu n là một hợp số dương lẻ thì tồn tại không quá (n − 1)/4 cơ sở b, 1 ≤ b ≤ n − 1, sao cho n trải qua đuợc kiểm tra Miller. Ta kết luận số n là số nguyên tố nếu nó trải qua được kiểm tra Miller với hơn (n − 1)/4 cơ sở. Nếu n là hợp số và số b được chọn ngẫu nhiên sao cho 1 ≤ b ≤ n − 1, thì xác suất để n trải qua được kiểm tra Miller cơ sở b sẽ không quá 1/4. Nếu n là hợp số và k số được chọn ngẫu nhiên trong {1, , n − 1}, thì xác suất để n trải qua được kiểm tra Miller đối với k cơ sở này sẽ không quá 4−k. Với k đủ lớn (ví dụ k = 20), và n trải qua được kiểm tra Miller đối với k cơ sở ngẫu nhiên, thì ta có thể tin "gần như chắc chắn" n là số nguyên tố. Chương 2: Số nguyên 32/54
  33. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Thuật toán Rabin - Miller Thuật toán 1 [Xuất phát] Đặt c ← 20. Đặt t ← n − 1 và s ← 0. Nếu t còn chẵn thì đặt t ← t/2 và s ← s + 1. 2 [Chọn b mới] Chọn ngẫu nhiên số b trong khoảng 1 0 quay lại bước 2, ngược lại thì kết thúc với kết luận "n là số nguyên tố". Chương 2: Số nguyên 33/54
  34. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Các số giả ngẫu nhiên Các số ngẫu nhiên trên máy tính thường được sinh một cách có hệ thống, nghĩa là bằng một phương pháp nào đó. Dãy số ngẫu nhiên được sinh một cách có hệ thống dĩ nhiên không phải là được chọn ngẫu nhiên. Khi biết số xuất phát, dãy hoàn toàn xác định. Một ví dụ là phương pháp bình phương - ở giữa của Von Neumann. Để sinh các số ngẫu nhiên có 4 chữ số, ta bắt đầu bởi một số tùy ý, chẳng hạn 9011. Bình phương số này, ta được 81198121. Lấy các số ở giữa là 1981. Các số nguyên trong dãy được sinh bởi một phương pháp nào đó, nhưng xuất hiện ngẫu nhiên, được gọi là các số giả ngẫu nhiên. Độ dài lớn nhất của dãy số ngẫu nhiên mà không có số lặp lại được gọi là độ dài tuần hoàn của dãy. Chương 2: Số nguyên 34/54
  35. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Phương pháp đồng dư tuyến tính Chọn các số nguyên m, a, c, x0 sao cho m > 0, 2 ≤ a ≤ m, 0 ≤ c ≤ m, 0 ≤ x0 ≤ m. Dãy các số giả ngẫu nhiên xác định bởi công thức xn+1 ≡ axn + c mod m Định lý Các số giả ngẫu nhiên sinh bởi phương pháp đồng dư tuyến tính cho ak − 1 bởi công thức x ≡ akx + c mod m k 0 a − 1 Định lý Với phương pháp đồng dư tuyến tính, dãy nhận được có độ dài tuần hoàn m nếu và chỉ nếu gcd(c, m) = 1, a ≡ 1 mod p với mọi ước nguyên tố p của m, và a ≡ 1 mod 4 nếu 4|m. Chương 2: Số nguyên 35/54
  36. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Định lý cơ bản của số học Định lý Mọi số nguyên lớn hơn 1 đều phân tích được một cách duy nhất thành tích các số nguyên tố, trong đó các thừa số được viết với thứ tự không giảm. r1 r2 rt n = p1 p2 pt Phân tích trên của các số nguyên được gọi là phân tích ra thừa số nguyên tố. Phân tích một số nguyên lớn ra thừa số nguyên tố là một bài toán khó của số học. Bài toán đặt ra: Thuật toán phân tích một số nguyên ra thừa số nguyên tố. Thuật toán phân tích một số nguyên lớn n ra thừa số nguyên tố. Chương 2: Số nguyên 36/54
  37. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Câu hỏi Chứng minh rằng nếu√ ước nguyên tố bé nhất p của số nguyên 3 n dương n vượt quá n thì p là số nguyên tố. Chứng minh rằng nếu p1 = 6m + 1, p2 = 12m + 1, p3 = 18m + 1 là các số nguyên tố thì p1p2p3 là một số Carmichael. Chứng minh rằng n = 6601 là một số Carmichael. Chứng minh rằng n = 2047 = 23.89, là một số giả nguyên tố mạnh cơ sở 2. Giả sử p là số nguyên tố. Chứng minh rằng a2 ≡ 1 mod p khi và chỉ khi a ≡ ±1 mod p. Trình bày thuật toán kiểm tra số nguyên tố với xác suất bị sai không quá 0.000001. Chương 2: Số nguyên 37/54
  38. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Ước số chung lớn nhất Định nghĩa Ước số chung lớn nhất của hai (hoặc nhiều) số nguyên không đồng thời bằng không, là số nguyên dương lớn nhất chia hết các số này. Ký hiệu: gcd(a, b), gcd(a1, a2, , an). Hai số nguyên được gọi là nguyên tố cùng nhau nếu ước số chung lớn nhất của chúng bằng 1. Mọi ước chung của a và b đều chia hết gcd(a, b). gcd(a, 0) = |a|, với a 6= 0. gcd(a + mb, b) = gcd(a, b), với m ∈ Z. Nếu m > 0, thì gcd(ma, mb) = m gcd(a, b). a b gcd(a,b) Nếu m là một ước chung của a và b, thì gcd( m , m ) = m . Chương 2: Số nguyên 38/54
  39. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Thuật toán Euclide Thuật toán (Euclide) 1 [Kết thúc] Nếu b = 0, dừng với kết quả là a. 2 [Chia Euclide] Tính r ← a mod b, và đặt a ← b, b ← r. Quay lại bước 1. Định lý (Lamé) Số phép chia cần thiết để tìm ước chung lớn nhất của hai số nguyên dương bằng thuật toán Euclide không vượt quá 5 lần số chữ số thập phân của số bé trong hai số đã cho. Hệ quả. Giả sử a < b, khi đó số các phép tính bit cần thiết để 3 thực hiện thuật toán Euclide là O((log2 a) ). Chương 2: Số nguyên 39/54
  40. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Thuật toán J. Stein Thuật toán J. Stein tìm ước số chung lớn nhất của hai số nguyên được biểu diễn dưới dạng nhị phân. Các phép chia 2 của thuật toán J. Stein được thực hiện bằng thao tác dịch bit sang phải. Thuật toán J. Stein dựa trên những nhận xét sau:  a b  1 Nếu a, b là các số chẵn, thì gcd(a, b) = 2 gcd , . 2 2  a  2 Nếu a chẵn, b lẻ, thì gcd(a, b) = gcd , b . 2 3 Nếu a, b đều lẻ thì a − b chẵn và |a − b| < max(a, b). 4 gcd(a, b) = gcd(a − b, b). Chương 2: Số nguyên 40/54
  41. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Thuật toán J. Stein Thuật toán 1 [Tìm lũy thừa 2] Đặt k ← 0. Lặp lại các phép tính sau cho đến khi ít nhất một trong hai số a, b lẻ: k ← k + 1, a ← a/2, b ← b/2 2 [Xuất phát] Nếu a lẻ, đặt t ← −b và chuyển sang bước 4. Ngược lại, đặt t ← a. 3 [Chia đôi t] Đặt t ← t/2. 4 [Kiểm tra t chẵn] Nếu t chẵn, quay lại bước 3. 5 [Sắp xếp lại] Nếu t > 0, đặt a ← t. Ngược lại, đặt b ← −t. 6 [Kết thúc] Đặt t ← a − b. Nếu t 6= 0, quay lại bước 3. Ngược lại, kết thúc vói kết quả là a2k. Chương 2: Số nguyên 41/54
  42. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Thuật toán Euclide mở rộng Định lý Ước chung lớn nhất của hai số nguyên a và b là số d dương nhỏ nhất biểu diễn được dưới dạng tổ hợp tuyến tính của a và b. Trong một số trường hợp, ta không chỉ cần tìm ước chung lớn nhất của hai số nguyên, mà còn muốn tìm biểu diễn của ước chung này dưới dạng tổ hợp tuyến tính của hai số nguyên ban đầu. Tiêu biểu là bài toán tìm nghịch đảo của một số nguyên theo modulo n. Thuật toán Euclide mở rộng nhận đầu vào là hai số nguyên a, b, và cho kết quả là bộ số (m, n, d) sao cho gcd(a, b) = d = ma + nb Chương 2: Số nguyên 42/54
  43. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Thuật toán Euclide mở rộng Thuật toán 1 [Xuất phát] Đặt (m, n, d) ← (1, 0, a) và (u1, u2, u3) ← (1, 0, b). 2 [Kết thúc] Nếu u3 = 0, kết thúc thuật toán.  d  3 [Tính toán] Đặt q = , và đặt u3 (v1, v2, v3) ← (m, n, d) − q(u1, u2, u3) (m, n, d) ← (u1, u2, u3), (u1, u2, u3) ← (v1, v2, v3) và quay lại bước 2. Ở mỗi lần lặp, thuật toán đều đảm bảo các đẳng thức sau ma + nb = d, u1a + u2b = u3, v1a + v2b = v3 Chương 2: Số nguyên 43/54
  44. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Câu hỏi Chứng minh rằng một số nguyên x biểu diễn được dưới dạng tổ hợp tuyến tính của a và b khi và chỉ khi x sẽ chia hết cho ước số chung lớn nhất của a, b. Chứng minh rằng tồn tại vô số cặp (x, y) ∈ Z2 sao cho ax + by = d với d là ước số chung lớn nhất của a và b. Chứng minh rằng gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c). Chứng minh rằng tồn tại x, y, z ∈ Z sao cho ax + by + cz = gcd(a, b, c). Chứng minh rằng gcd(ma1, ma2, , mak) = m gcd(a1, a2, , ak) với m > 0 nào đó. Chương 2: Số nguyên 44/54
  45. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Định lý Trung Quốc về phần dư Định lý Nếu m1, m2, , mr là các số nguyên dương nguyên tố cùng nhau từng cặp, thì hệ phương trình đồng dư x ≡ a1 mod m1 x ≡ ar mod mr có nghiệm duy nhất theo modulo M = m1m2 mr. Ta có gcd(Mk, mk) = 1 với Mk = m1m2 mk−1mk+1 mr. Tồn tại yk sao cho ykMk ≡ 1 mod mk. Nghiệm của hệ là x = a1y1M1 + a2y2M2 + + aryrMr. 0 0 Nếu x và x là hai nghiệm phân biệt của hệ thì x ≡ ak ≡ x 0 mod mk. Suy ra x ≡ x mod M. Chương 2: Số nguyên 45/54
  46. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Định lý Trung Quốc về phần dư Khi cho trước các module nguyên tố cùng nhau m1, m2, , mr, một số dương n < M = m1m2 mr được xác định duy nhất bởi các thặng dư của nó theo modulo mj với j = 1, 2, , r. Chẳng hạn ta có các máy tính với cỡ từ 100, và các module nguyên tố cùng nhau là m1 = 99, m2 = 98, m3 = 97, m4 = 95. Khi đó, các số nguyên bé hơn M = 99.98.97.95 = 89403930 được biểu diễn duy nhất thành bộ 4 số theo modulo m1, m2, m3, m4. Để cộng các số nguyên n1, n2 < M, ta chỉ cần cộng các thặng dư của chúng theo modulo m1, m2, , mr. Chẳng hạn số x = 123684 được biểu diễn bởi (33, 8, 9, 89) mod (99, 98, 97, 95), số y = 413456 được biểu diễn bởi (32, 92, 42, 16) mod (99, 98, 97, 95). Như vậy, x + y được biểu diễn bởi (65, 2, 51, 10) mod (99, 98, 97, 95). Dùng định lý Trung Quốc về phần dư, ta tính được x + y ≡ 537140 mod 89403930. Chương 2: Số nguyên 46/54
  47. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Tính toán các số nguyên lớn trên máy tính Bổ đề Nếu a và b là các số nguyên dương thì thặng dư bé nhất modulo 2b − 1 của 2a − 1 là 2r − 1, trong đó r là thặng dư bé nhất của a modulo b. Nghĩa là nếu a ≡ r mod b, thì 2a − 1 ≡ 2r − 1 mod 2b − 1. Hệ quả. Nếu a và b là các số nguyên dương, thì gcd(2a − 1, 2b − 1) = 2gcd(a,b) − 1. Hệ quả. gcd(2a − 1, 2b − 1) = 1 khi và chỉ khi gcd(a, b) = 1. Hệ cơ số của máy tính là hệ cơ số nhị phân, và cỡ từ của máy tính thường là một lũy thừa của 2, chẳng hạn 232 hoặc 264. Để có thể biểu diễn và tính toán với các số nguyên có cỡ lớn hơn cỡ từ của máy, ta có thể chọn các module nguyên tố cùng nhau có dạng 2a − 1 sao cho tích của các module này đạt (hoặc vượt) cỡ của các số nguyên đó. Chương 2: Số nguyên 47/54
  48. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Câu hỏi Trên một máy tính có cỡ từ là 25, có thể áp dụng định lý Trung Quốc về phần dư để biểu diễn các số có 14-bit được không? Trong số các số không quá 28, tìm x thỏa hệ phương trình đồng dư x ≡ 3 mod 4, x ≡ 4 mod 5, và x ≡ 6 mod 7. Giả sử n|ab nhưng n 6 |a và n 6 |b. Chứng minh rằng 1 < gcd(a, n) < n và 1 < gcd(b, n) < n. Chương 2: Số nguyên 48/54
  49. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Phân số liên tục Định nghĩa a Giả sử a và b là các số nguyên dương, a > b. Khi đó, phân số có b thể viết dưới dạng a c 1 = a + 0 = a + b 0 b 0 b c0 a c 1 = a + 0 = a + b 0 b 0 1 a + 1 1 a + 2 . a Cách viết trên được gọi là dạng phân số liên tục của số hữu tỷ . b Chương 2: Số nguyên 49/54
  50. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Phân số liên tục a 1 1 Ký hiệu = [a0; a1, a2, ] = a0 + + + = b a1+ a2+ a0 + 1/(a1 + 1/(a2 + 1/( ))). Phân số liên tục [a0; a1, a2, , an] được gọi là phân số liên tục hữu hạn. Một số hữu tỷ bất kỳ có thể được biểu diễn dưới dạng phân số liên tục hữu hạn. Một số thực bất kỳ có thể biểu diễn dưới dạng phân số liên tục, hữu hạn hoặc vô hạn. Giả sử x = [a0; a1, a2, , an, ], phân số hội tụ riêng thứ k của x là các số Ck = [a0; a1, a2, , ak] . Chương 2: Số nguyên 50/54
  51. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Các tính chất Định lý Giả sử a0, a1, , an là các số thực, trong đó a0, a1, , an > 0. Đặt p0 = a0, q0 = 1 p1 = a0a1 + 1, q1 = a1 pk = akpk−1 + pk−2, qk = akqk−1 + qk−2 pk Khi đó ta có Ck = [a0; a1, a2, , ak] = . qk Định lý Ta có i) C1 > C3 > C5 > ii) C0 C2k với mọi j, k iv) lim Ck = x k→∞ Chương 2: Số nguyên 51/54
  52. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Các tính chất Định lý k+1 Với mọi k ≥ 1, ta có: pkqk+1 − pk+1qk = (−1) . Từ đó ta suy ra rằng, các số pk, qk nguyên tố cùng nhau. Định lý p Giả sử n là một số tự nhiên không chính phương và k là các phân số √ √ qk hội tụ riêng của n. Đặt α0 = n, P0 = 0, Q0 = 1, và các số αk, Qk, Pk được định nghĩa như sau: √ Pk + n Pk+1 = akQk − Pk αk = Qk 2 ak = bαkc Qk+1 = (n − Pn+1)/Qk 2 2 k−1 Khi đó ta có: pk − nqk = (−1) Qk+1. Chương 2: Số nguyên 52/54
  53. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Phân tích thừa số nguyên tố Nếu tìm được các số x, y sao cho x − y 6= 1 và x2 − y2 = n thì ta tìm được ước số không tầm thường của n. Nếu tìm được các số x, y sao cho 0 < x < y < n, x + y 6= n, và x2 ≡ y2 mod n thì gcd(x − y, n) và gcd(x + y, n) là các ước không tầm thường của n, vì n|(x + y)(x − y) nhưng n 6 |(x + y) và n 6 |(x − y). Theo định lý trên ta có 2 k−2 pk−1 ≡ (−1) Qk mod n Nếu tìm được số Qk là một số chính phương với k chẵn, thì có thể tìm được một ước số không tầm thường của n. Chương 2: Số nguyên 53/54
  54. Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Câu hỏi pk Giả sử Ck = là các phân số hội tụ riêng của [a0; a1, a2, , an]. qk Chứng minh rằng với mọi k trong khoảng [1, n], ta có qk−1 ≤ qk. √ √ √ 1 + 5 Tìm biểu diễn phân số liên tục của 2, 5, và . 2 Tìm phân số hữu tỷ biểu diễn bởi [−2; 2, 4, 6, 8] và [4; 2, 1, 3, 1, 2, 4]. Giả sử x = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ]. Tìm C8. Trong số các k thỏa pk(x) < 100, tìm k sao cho |x − Ck(x)| là bé nhất. Chương 2: Số nguyên 54/54