Bài giảng Nhập môn Số học thuật toán: Chương 3, 4, 5 - Nguyễn Đạt Thông

Bài giảng Nhập môn Số học thuật toán - Chương 3, 4, 5 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. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Nhập môn Số học thuật toán: Chương 3, 4, 5 - Nguyễn Đạt Thông Các hàm số học Thặng dư bình phương Đường cong Elliptic Chương 3 CÁC HÀM SỐ HỌC 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 3: Các hàm số học 1/45 Các hàm số học Thặng dư bình phương Đường cong Elliptic Hàm số học Định nghĩa Hàm số học là hàm xác định trên tập hợp các số nguyên dương. f: N∗ −→ N∗ n 7−→ f (n) Định nghĩa Một hàm số học f được gọi là nhân tính nếu với mọi m, n nguyên tố cùng nhau, ta có f (mn) = f (m)f (n). Trong trường hợp đẳng thức đúng với mọi m, n, hàm f được gọi là nhân tính mạnh. Các hàm nhân tính mạnh đơn giản nhất là f (n) = n và f (n) = 1. Nếu n = pr11 pr22 ...prkk thì f (n) = f (pr11 )f (pr22 )...f (prkk ), trong đó f là một hàm nhân tính. X Nếu f nhân tính thì F (n) = f (d) cũng nhân tính. d|n Chương 3: Các hàm số học 2/45 Các hàm số học Thặng dư bình phương Đường cong Elliptic Phi hàm Euler Định nghĩa Phi hàm Euler φ(n) là hàm số học có giá trị tại n, bằng số các số không vượt quá n và nguyên tố cùng nhau với n. Định nghĩa Hệ thặng dư thu gọn modulo n là tập hợp gồm φ(n) số nguyên sao cho mỗi phần tử của tập hợp nguyên tố cùng nhau với n, và không có hai phần tử nào đồng dư với nhau modulo n. Định lý Nếu r1 , r2 , ..., rφ(n) là một hệ thặng dư thu gọn modulo n, và a là số nguyên dương thỏa gcd(a, n) = 1, thì tập hợp ar1 , ar2 , ..., arφ(n) cũng là một hệ thặng dư thu gọn modulo n. Chương 3: Các hàm số học 3/45 Các hàm số học Thặng dư bình phương Đường cong Elliptic Định lý Euler Định lý (Euler) Nếu n là số nguyên dương và a là số nguyên tố cùng nhau với n thì aφ(n) ≡ 1 mod n Số p là nguyên tố khi và chỉ khi φ(p) = p − 1. Với mọi số nguyên tố p, ta có φ(pk ) = pk − pk−1 . Phi hàm Euler là hàm nhân tính. Nghĩa là φ(mn) = φ(m)φ(n).     r1 r2 rk 1 1 Nếu n = p1 p2 ...pk thì φ(n) = n 1 − ... 1 − . p1 pk X Với mọi số nguyên dương n, ta có φ(d) = n. d|n Chương 3: Các hàm số học 4/45 Các hàm số học Thặng dư bình phương Đường cong Elliptic Ví dụ về phi hàm Euler φ(1) = 1 φ(2) = 1 φ(3) = 2 φ(4) = 2. φ(5) = 5 − 1 = 4 φ(7) = 7 − 1 = 6 φ(11) = 11 − 1 = 10. φ(6) = φ(2)φ(3) = 2 φ(10) = φ(2)φ(5) = 4 φ(30) = φ(2)φ(3)φ(5) = 8. φ(8) = φ(23 ) = 23 − 22 = 4 φ(9) = φ(32 ) = 32 − 3 = 6. 2φ(7) = 26 = 64 ≡ 1 mod 7. Chương 3: Các hàm số học 5/45 Các hàm số học Thặng dư bình phương Đường cong Elliptic Đồng dư của lũy thữa lớn Các tính chất của Phi hàm Euler được sử dụng để tính đồng dư của những lũy thừa rất lớn. Cụ thể, ta cần tính an mod k, trong đó n là một số nguyên lớn. Giả sử ta có k = pr11 pr22 ...prss . ri Trong đó aφ(pi ) ≡ 1 mod pri i , với i = 1, 2, ..., s. Đặt N là bội số chung nhỏ nhất của các φ(pri i ) thì aN ≡ 1 mod k. Nếu n ≡ r mod N thì an ≡ ar mod k. 6 Một ví dụ cụ thể là tính 210 mod 77. 77=11.7, φ(11) = 10, φ(7) = 6. Bội chung nhỏ nhất của 10 và 6 là 30. Ta có 230 ≡ 1 mod 77. 6 Do 106 ≡ 10 mod 30 nên 210 ≡ 210 ≡ 23 mod 77. Chương 3: Các hàm số học 6/45 Các hàm số học Thặng dư bình p ...