›
›

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

pdf 45 trang ngocly 3340
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 - Chương 3: Các hàm số học - 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_chuong_3_cac_ham_so.pdf

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

  1. 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
  2. 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. r1 r2 rk r1 r2 rk Nếu n = p1 p2 pk thì f(n) = f(p1 )f(p2 ) f(pk ), 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
  3. 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
  4. 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
  5. 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
  6. 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. r1 r2 rs Giả sử ta có k = p1 p2 ps . ri r φ(pi ) i Trong đó a ≡ 1 mod pi , với i = 1, 2, , s. ri N Đặt N là bội số chung nhỏ nhất của các φ(pi ) thì a ≡ 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
  7. Các hàm số học Thặng dư bình phương Đường cong Elliptic Hàm τ và hàm σ Định nghĩa Hàm τ(n) có giá trị tại n, bằng số các ước dương của n. Hàm σ(n) có giá trị tại n, bằng tổng các ước dương của n. X X τ(n) = 1, σ(n) = d d|n d|n τ(n) và σ(n) là các hàm nhân tính. r1 r2 rk Giả sử n = p1 p2 pk . Khi đó k rj +1 Y pj − 1 σ(n) = pj − 1 j=1 k Y τ(n) = (rj + 1) j=1 Chương 3: Các hàm số học 7/45
  8. Các hàm số học Thặng dư bình phương Đường cong Elliptic Số hoàn hảo Định nghĩa Số nguyên dương n được gọi là số hoàn hảo nếu σ(n) = 2n. Định lý Số nguyên dương chẵn n là số hoàn hảo khi và chỉ khi n = 2m−1(2m − 1) với m ≥ 2 là số nguyên sao cho 2m − 1 là số nguyên tố. Các số 6, 28, 496, 8128 là các số hoàn hảo. Với mỗi số nguyên tố p = 2m − 1, ta có một số hoàn hảo. Người ta biết được rằng, trong khoảng từ 1 đến 10200 không có số hoàn hảo lẻ. Tuy nhiên, tồn tại hay không các số hoàn hảo lẻ? Chương 3: Các hàm số học 8/45
  9. Các hàm số học Thặng dư bình phương Đường cong Elliptic Số hoàn hảo Mỗi số hoàn hảo có thể biểu diễn dưới dạng tổng các số tự nhiên liên tiếp. 6 = 1 + 2 + 3 28 = 1 + 2 + 3 + 4 + 5 + 6 + 7 496 = 1 + 2 + 3 + + 30 + 31 8128 = 1 + 2 + 3 + + 126 + 127 Tổng đảo của tất cả các ước số của số hoàn hảo đều bằng 2. 1 1 1 1 + + + = 2 2 3 6 1 1 1 1 1 1 + + + + + = 2 2 4 7 14 28 1 1 1 1 1 1 1 1 1 1 + + + + + + + + + = 2 2 4 8 16 31 62 124 248 496 Biểu diễn các số hoàn hảo dưới hệ nhị phân. 6 = 110 28 = 11100 496 = 111110000 8128 = 1111111000000 Chương 3: Các hàm số học 9/45
  10. Các hàm số học Thặng dư bình phương Đường cong Elliptic Số nguyên tố Mersenne Định nghĩa m Với m là một số nguyên dương, Mm = 2 − 1 được gọi là số Mersenne thứ m. Nếu p là số nguyên tố, và Mp cũng là số nguyên tố, thì Mp được gọi là số nguyên tố Mersenne. Định lý Nếu p là một số nguyên tố lẻ, thì mọi ước nguyên tố của số Mersenne Mp đều có dạng 2kp + 1 với k là số nguyên dương. Các số M2, M3, M5, M7 là các số nguyên tố Mersenne, trong khi M11 là hợp số. 13 Xét √M13 = 2 − 1 = 8191, mọi ước nguyên của M13 không vượt quá M13 ≈ 90 (nếu có) đều phải ở dạng 26k + 1. Do 53 và 79 không phải là ước của M13 nên ta kết luận M13 là số nguyên tố. Chương 3: Các hàm số học 10/45
  11. Các hàm số học Thặng dư bình phương Đường cong Elliptic Bậc theo modulo n Định nghĩa Giả sử a và n là các số nguyên dương nguyên tố cùng nhau. Khi đó số nguyên dương nhỏ nhất x thỏa ax ≡ 1 mod n được gọi là bậc của a theo modulo n. Ký hiệu: x = ordn a. Định lý Giả sử a và n > 0 là các số nguyên tố cùng nhau. Khi đó số nguyên x là nghiệm của phương trình đồng dư ax ≡ 1 mod n khi và chỉ khi x chia hết cho bậc của a theo modulo n. Hệ quả. ordn a chia hết φ(n). i j Hệ quả. a ≡ a mod n ⇔ i ≡ j mod ordn a Bậc của a theo modulo n luôn tồn tại vì theo định lý Euler, aφ(n) ≡ 1 mod n. Bậc của a theo modulo n không vượt quá φ(n). Chương 3: Các hàm số học 11/45
  12. Các hàm số học Thặng dư bình phương Đường cong Elliptic Căn nguyên thủy Định nghĩa Nếu r và n > 0 là các số nguyên tố cùng nhau và ordn r = φ(n) thì r được gọi là căn nguyên thủy modulo n. Định lý Nếu r là căn nguyên thủy theo modulo n > 0 thì các số sau lập thành hệ thặng dư thu gọn modulo n: r1, r2, , rφ(n) u ordn r Với u là một số nguyên dương, ta có ordn r = . gcd(u, ordn r) Với r là căn nguyên thủy modulo n > 0, ru là căn nguyên thủy modulo n khi và chỉ khi gcd(u, φ(n)) = 1. Nếu số nguyên dương n có căn nguyên thủy, thì nó có tất cả φ(φ(n)) căn nguyên thủy không đồng dư nhau. Chương 3: Các hàm số học 12/45
  13. Các hàm số học Thặng dư bình phương Đường cong Elliptic Định lý Lagrange Định lý (Lagrange) n n−1 Giả sử f(x) = anx + an−1x + + a1x + a0 là đa thức với hệ số nguyên modulo số nguyên tố p, đồng thời n > 0 và an 6≡ 0 mod p. Khi đó f(x) có nhiều nhất n nghiệm modulo p không đồng dư từng cặp. Định lý Giả sử p là số nguyên tố và d là một ước dương của p − 1. Khi đó đa thức xd − 1 có đúng d nghiệm modulo p không đồng dư từng cặp. Định lý Giả sử p là số nguyên tố và d là một ước dương của p − 1. Khi đó số các số nguyên không đồng dư có bậc d modulo p là φ(d). Hệ quả. Mọi số nguyên tố đều có căn nguyên thủy. Chương 3: Các hàm số học 13/45
  14. Các hàm số học Thặng dư bình phương Đường cong Elliptic Sự tồn tại của căn nguyên thủy Định lý Nếu p là một số nguyên tố lẻ với căn nguyên thủy r, thì hoặc r, hoặc r + p là căn nguyên thủy modulo p2. Định lý Giả sử p là một số nguyên tố lẻ, khi đó pk có căn nguyên thủy với mọi số dương k. Hơn nữa, nếu r là căn nguyên thủy modulo p2 thì r là căn nguyên thủy modulo pk với mọi số nguyên dương k. Định lý Nếu số nguyên dương n không phải là lũy thừa của một số nguyên tố hoặc hai lần lũy thừa của một số nguyên tố, thì n không có căn nguyên thủy. Chương 3: Các hàm số học 14/45
  15. Các hàm số học Thặng dư bình phương Đường cong Elliptic Sự tồn tại của căn nguyên thủy Định lý Nếu p là số nguyên tố lẻ và t là số nguyên dương, thì 2pt có căn nguyên thủy. Cụ thể nếu r là căn nguyên thủy modulo pt thì: r là căn nguyên thủy modulo 2pt khi r lẻ. r + pt là căn nguyên thủy modulo 2pt khi r chẵn. Định lý Nếu a là số nguyên tố lẻ, k ≥ 3 là số nguyên thì k k−2 aφ(2 )/2 = a2 ≡ 1 mod 2k Định lý Số nguyên dương n có căn nguyên thủy khi và chỉ khi n = 2, 4, pt, 2pt, trong đó p là số nguyên tố lẻ và t là một số nguyên dương. Chương 3: Các hàm số học 15/45
  16. Các hàm số học Thặng dư bình phương Đường cong Elliptic Câu hỏi Tìm tất cả các số tự nhiên n thỏa σ(n) + φ(n) = 2n. √ Chứng minh rằng n là một hợp số khi và chỉ khi σ(n) > n + n. X k Chứng minh rằng σk(n) = d là hàm nhân tính. d|n Chứng minh rằng nếu p, q là các số nguyên tố lẻ khác nhau thì, n = pq là số giả nguyên tố cơ sở 2 khi và chỉ khi ordq 2|(p − 1) và ordp 2|(q − 1). Chứng minh rằng nếu p, q là các số nguyên tố lẻ khác nhau thì, n = pq là số giả nguyên tố cơ sở 2 khi và chỉ khi p q MpMq = (2 − 1)(2 − 1) là số giả nguyên tố cơ sở 2. Chương 3: Các hàm số học 16/45
  17. Các hàm số học Thặng dư bình phương Đường cong Elliptic Câu hỏi Chứng minh rằng hai số nguyên có tích các ước số khác nhau thì hai số nguyên đó khác nhau. Chứng minh rằng nếu n chia hết cho 24 thì σ(n) cũng chia hết cho 24. Chứng minh rằng với mọi k > 1, phương trình τ(x) = k có vô số nghiệm. Chứng minh rằng nếu m có căn nguyên thủy thì phương trình x2 ≡ 1 mod m chỉ có nghiệm x ≡ ±1 mod m. Giả sử n là một số có căn nguyên thủy. Chứng minh rằng tích của các số nguyên dương nhỏ hơn n và nguyên tố cùng nhau với n đồng dư −1 theo modulo n. Chương 3: Các hàm số học 17/45
  18. Các hàm số học Thặng dư bình phương Đường cong Elliptic Chương 4 THẶNG DƯ BÌNH PHƯƠNG 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 4: Thặng dư bình phương 18/45
  19. Các hàm số học Thặng dư bình phương Đường cong Elliptic Thặng dư bình phương Định nghĩa Giả sử n là một số nguyên dương. Số a được gọi là một thặng dư bình phương của n nếu gcd(a, n) = 1 và đồng dư x2 ≡ a mod n có nghiệm. Ngược lại, ta nói a là không thặng dư bình phương của n. Bổ đề Giả sử p là một số nguyên tố lẻ, a là số nguyên không chia hết cho p. Khi đó đồng dư x2 ≡ a mod p, hoặc không có nghiệm, hoặc có đúng hai nghiệm không đồng dư modulo p. Định lý p − 1 Nếu p là một số nguyên tố lẻ, trong các số 1, 2, , p − 1 có đúng 2 thặng dư bình phương. Chương 4: Thặng dư bình phương 19/45
  20. Các hàm số học Thặng dư bình phương Đường cong Elliptic Ký hiệu Legendre Định nghĩa Giả sử p là một số nguyên tố lẻ và a là một số nguyên không chia hết a cho p, ký hiệu Legendre được định nghĩa như sau p a  1, nếu a là thặng dư bình phương modulo p = p −1, nếu ngược lại. Ví dụ với số nguyên tố p = 11, ta có:  1   3   4   5   9  = = = = = 1 11 11 11 11 11  2   6   7   8   10  = = = = = −1 11 11 11 11 11 Chương 4: Thặng dư bình phương 20/45
  21. Các hàm số học Thặng dư bình phương Đường cong Elliptic Tiêu chuẩn Euler Định lý (Tiêu chuẩn Euler) Giả sử p là một số nguyên tố lẻ, và a là số nguyên dương không chia hết cho p. Khi đó a p−1 ≡ a 2 mod p p Định lý Giả sử p là một số nguyên tố lẻ, a và b là các số nguyên không chia hết cho p. Khi đó: a  b  (i) Nếu a ≡ b mod p thì = . p p a  b  ab a2  (ii) = . (iii) = 1. p p p p Chương 4: Thặng dư bình phương 21/45
  22. Các hàm số học Thặng dư bình phương Đường cong Elliptic Một số tính chất khác Định lý Nếu p là số nguyên tố lẻ thì −1  1, khi p ≡ 1 mod 4 = p −1, khi p ≡ −1 mod 4 Định lý (Bổ đề Gauss) Giả sử p là số nguyên tố lẻ và gcd(a, p) = 1. Nếu s là số thặng dư bé a nhất của các số nguyên a, 2a, , p−1 a lớn hơn p , thì = (−1)s. 2 2 p Định lý 2 p2−1 Nếu p là một số nguyên tố lẻ thì = (−1) 8 . p Chương 4: Thặng dư bình phương 22/45
  23. Các hàm số học Thặng dư bình phương Đường cong Elliptic Luật thuận nghịch bình phương Định lý (Luật thuận nghịch bình phương) Giả sử p và q là các số nguyên tố lẻ, khi đó ta có p  q  p−1 q−1 = (−1) 2 2 q p . Bổ đề Giả sử p là một số nguyên tố lẻ, a là một số lẻ không chia hết cho p. p−1 a X2 ja Khi đó = (−1)T (a,p), trong đó T (a, p) = . p p j=1 Chương 4: Thặng dư bình phương 23/45
  24. Các hàm số học Thặng dư bình phương Đường cong Elliptic Một số áp dụng luật thuận nghịch bình phương Áp dụng để tính giá trị của các ký hiệu Legendre.  p   −q  = nếu p ≡ q ≡ 3 mod 4. q p  p   q  = nếu p ≡ 1 mod 4 hoặc q ≡ 1 mod 4. q p  713  23.31  23   31  Ví dụ để tính = = . 1009 1009 1009 1009 Ta có:  23   1009   20   225   5   23   3  = = = = = = = 1009 23 23 23 23 5 5  5   2  = = −1. 3 3  31  = −1 1009  713  Suy ra = 1 1009 Chương 4: Thặng dư bình phương 24/45
  25. Các hàm số học Thặng dư bình phương Đường cong Elliptic Một số áp dụng luật thuận nghịch bình phương 2m Áp dụng để chứng minh kiểm tra Pepin: Số Fermat Fm = 2 + 1 là số nguyên tố khi và chỉ khi Fm−1 3 2 ≡ −1 mod Fm Chiều thuận: Fm−1 Giả thiết suy ra 3 ≡ 1 mod Fm. Fm−1 Do đó nếu Fm có ước nguyên tố p thì 3 ≡ 1 mod p. 2m Suy ra ordp 3|Fm − 1 = 2 . m−1 Fm−1 2 Mặt khác từ giả thiết cũng suy ra ordp 3 6 | 2 = 2 . 2m Vậy ordp 3 = 2 = Fm − 1. Từ đó ta có Fm − 1 ≤ p − 1. Nhưng vì p|Fm, nên Fm = p là số nguyên tố. Chiều nghịch:  3   F   2  Luật thuận nghịch: = m = = −1. Fm 3 3   3 Fm−1 Tiêu chuẩn Euler: ≡ 3 2 mod Fm. Fm Chương 4: Thặng dư bình phương 25/45
  26. Các hàm số học Thặng dư bình phương Đường cong Elliptic Ký hiệu Jacobi Định nghĩa Giả sử n là số nguyên dương lẻ, a nguyên tố cùng nhau với n. Nếu n r1 r2 rm có phân tích ra thừa số nguyên tố là p1 p2 pm , ta định nghĩa ký hiệu Jacobi như sau: h a i  a r1  a r2  a rm = n p1 p2 pm trong đó ở vế phải là các ký hiệu Legendre. Nếu n là số nguyên tố thì ký hiệu Jacobi trùng với ký hiệu Legendre. Ký hiệu Jacobi không cho biết phương trình đồng dư x2 ≡ a mod n có nghiệm hay không. Ký hiệu Jacobi và ký hiệu Legendre có nhiều tính chất tương tự nhau. Chương 4: Thặng dư bình phương 26/45
  27. Các hàm số học Thặng dư bình phương Đường cong Elliptic Một số tính chất của ký hiệu Jacobi Định lý Giả sử n là số nguyên dương lẻ, a và b là các số nguyên tố cùng nhau với n. Khi đó: ab h a i  b  (i) Nếu a ≡ b mod n thì (ii) = . h a i  b  n n n = . n n     2 −1 n−1 2 n −1 (iii) = (−1) 2 . (iv) = (−1) 8 . n n Định lý (Luật thuận nghịch bình phương đối với ký hiệu Jacobi) Giả sử m, n là các số nguyên dương lẻ và nguyên tố cùng nhau. Khi đó h n i hmi m−1 n−1 = (−1) 2 2 m n Chương 4: Thặng dư bình phương 27/45
  28. Các hàm số học Thặng dư bình phương Đường cong Elliptic Thuật toán tính ký hiệu Jacobi Giả sử a, b là hai số nguyên dương nguyên tố cùng nhau, a > b. Đặt R0 = a, R1 = b, và s1 R0 = R1q1 + 2 R2 s2 R1 = R2q2 + 2 R3 sn−2 Rn−3 = Rn−2qn−2 + 2 Rn−1 sn−1 Rn−2 = Rn−1qn−1 + 2 .1 trong đó sj là các số nguyên không âm, Rj là số nguyên lẻ bé hơn Rj−1. Đặt: R2 − 1 R2 − 1 R2 − 1 R(a, b) = s 1 + s 2 + + s n−1 1 8 2 8 n−1 8 R − 1 R − 1 R − 1 R − 1 + 1 2 + + n−2 n−1 2 2 2 2 Chương 4: Thặng dư bình phương 28/45
  29. Các hàm số học Thặng dư bình phương Đường cong Elliptic Thuật toán tính ký hiệu Jacobi Định lý Giả sử a, b là các số nguyên dương và a > b. Khi đó ta có hai = (−1)R(a,b) b Hệ quả Giả sử a và b là các số nguyên dương nguyên tố cùng nhau, a > b. Khi hai đó, ký hiệu Jacobi có thể tính được với O((log b)3) phép tính bit. b 2 Số phép chia trong thuật toán xác định R(a, b) không vượt quá số phép chia trong thuật toán Euclid để tính gcd(a, b), nghĩa là không quá O(log2 b) phép chia. 2 Mỗi phép chia cần không quá O((log2 b) ) phép tính bit. Để xác định sj, cần O(log2 b) phép tính bit. 2 Để tính R(a, b), cần không quá O((log2 b) ) phép tính bit. Chương 4: Thặng dư bình phương 29/45
  30. Các hàm số học Thặng dư bình phương Đường cong Elliptic Số giả nguyên tố Euler Theo tiêu chuẩn Euler, nếu p là số nguyên tố lẻ và b không chia hết cho p thì p−1  b  b 2 ≡ mod p p Như vậy, nếu n và b nguyên tố cùng nhau và   n−1 b b 2 6≡ mod n, n trong đó vế phải là ký hiệu Jacobi, thì n phải là hợp số. Tuy nhiên, nếu đồng dư thức trên đúng, thì ta cũng không thể kết luận n là nguyên tố hay không. Định nghĩa Số nguyên dương n được gọi là số giả nguyên tố Euler cơ sở b nếu nó là hợp số và   n−1 b b 2 ≡ mod n, n Chương 4: Thặng dư bình phương 30/45
  31. Các hàm số học Thặng dư bình phương Đường cong Elliptic Số giả nguyên tố Fermat và số giả nguyên tố Euler Định lý Mọi số giả nguyên tố Euler cơ sở b đều là số giả nguyên tố Fermat cơ sở b. Điều ngược lại không đúng. Chẳng hạn số 431 là số giả nguyên tố Fermat cơ sở 2, nhưng không là số giả nguyên tố Euler cơ sở 2. Định lý Mọi số giả nguyên tố Fermat mạnh cơ sở b đều là số giả nguyên tố Euler cơ sở b. Điều ngược lại không đúng. Chẳng hạn số 1105 là số giả nguyên tố Euler cơ sở 2, nhưng không phải là số giả nguyên tố mạnh Fermat cơ sở 2. Chương 4: Thặng dư bình phương 31/45
  32. Các hàm số học Thặng dư bình phương Đường cong Elliptic Số giả nguyên tố Fermat và số giả nguyên tố Euler Định lý Số n giả nguyên tố Euler cơ sở b là số giả nguyên tố mạnh Fermat cơ  b  sở b nếu n ≡ 3 mod 4, hoặc = −1. n Bổ đề Giả sử n là một số nguyên dương lẻ không chính phương. Khi đó tồn  b  tại ít nhất một số b với 1 < b < n, gcd(b, n) = 1, sao cho = −1. n Bổ đề Với mỗi hợp số lẻ n, tồn tại ít nhất một số b sao cho 1 < b < n,   n−1 b gcd(b, n) = 1, và b 2 6≡ mod n. n Chương 4: Thặng dư bình phương 32/45
  33. Các hàm số học Thặng dư bình phương Đường cong Elliptic Thuật toán Solovay-Strassen Định lý φ(n) Đối với mỗi hợp số lẻ n, tồn tại không quá 2 số nguyên dương b nhỏ hơn n, nguyên tố cùng nhau với n, sao cho n là số giả nguyên tố Euler cơ sở b. Nếu n là hợp số lẻ, chọn b chọn ngẫu nhiên trong các số 1, 2, , 1 n − 1, thì xác suất để n giả nguyên tố Euler cơ sở b sẽ bé hơn 2 . Định lý (Thuật toán Solovay - Strassen) Cho n là một số nguyên dương. Chọn ngẫu nhiên k số b1, b2, , bk từ các số 1, 2, , n − 1. Với mỗi b, kiểm tra đồng dư thức sau n−1 b  b 2 ≡ j mod n j n Nếu n là số nguyên tố, mọi đồng dư thức đều đúng. Nếu n là hợp số, xác suất mọi đồng dư thức đúng sẽ bé hơn 1/2k. Chương 4: Thặng dư bình phương 33/45
  34. Các hàm số học Thặng dư bình phương Đường cong Elliptic Thuật toán Solovay-Strassen Với k đủ lớn và n trải qua được kiểm tra xác suất với k cơ sở ngẫu nhiên, thì hầu như chắc chắn n là số nguyên tố. Do mọi số giả nguyên tố mạnh Fermat cơ sở b đều là số giả nguyên tố Euler cơ sở b, nên số các số n trải qua được kiểm tra xác suất Rabin - Miller cũng sẽ trải qua được kiểm tra xác suất Solovay - Strassen. Ví dụ số n trải qua được kiểm tra xác suất Solovay - Strassen với k = 40 cơ số ngẫu nhiên khác nhau, thì xác suất để n là hợp số sẽ bé hơn 2−40. Chương 4: Thặng dư bình phương 34/45
  35. Các hàm số học Thặng dư bình phương Đường cong Elliptic Câu hỏi 1 Chứng minh rằng 1105 là số giả nguyên tố Euler cơ sở 2 và không giả nguyên tố mạnh Fermat cơ sở 2. 2 Chứng minh rằng nếu n là số giả nguyên tố Euler cơ sở a và b thì n cũng giả nguyên tố Euler cơ sở ab. 3 Chứng minh rằng nếu n là số giả nguyên tố Euler cơ sở b thì n cũng là số giả nguyên tố Euler cơ sở n − b. Chương 4: Thặng dư bình phương 35/45
  36. Các hàm số học Thặng dư bình phương Đường cong Elliptic Chương 5 ĐƯỜNG CONG ELLIPTIC 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 5: Đường cong Elliptic 36/45
  37. Các hàm số học Thặng dư bình phương Đường cong Elliptic Đường cong Elliptic Định nghĩa Đường cong Elliptic trên trường K là tập hợp các điểm (x, y) thỏa mãn phương trình 2 3 2 y + a1xy + a3y = x + a2x + a4x + a6 (1) hay 2 3 2 F (x, y) = y + a1xy + a3y − x − a2x − a4x − a6 = 0 (2) với một điểm O gọi là điểm vô cùng. Phương trình (1) phải thỏa mãn điều kiện không kỳ dị, tức là, tại mọi ∂F ∂F điểm (x, y), các đạo hàm riêng và không đồng thời bằng 0. ∂x ∂y Chương 5: Đường cong Elliptic 37/45
  38. Các hàm số học Thặng dư bình phương Đường cong Elliptic Đường cong Elliptic - Nhóm Abel Định lý Đường cong Elliptic được trang bị phép cộng và trở thành nhóm Abel như sau: Phần tử 0 là điểm tại vô cùng O. Điểm (x, y) có nghịch đảo là điểm (x, −y − a1x − a3). Hai điểm P = (xP , yP ) và Q = (xQ, yQ) không phải nghịch đảo của nhau thì R = P + Q, R = (xR, yR) được xác định như sau: xR = −xP − xQ − a2 + m(m + a1) yR = −yP − a3 − a1xR + m(xP − xR) trong đó y − y m = P Q nếu P 6= Q. xP − xQ 3x2 + 2a x + a − a y m = P 2 P 4 1 P nếu P = Q. 2yP + a1xP + a3 Chương 5: Đường cong Elliptic 38/45
  39. Các hàm số học Thặng dư bình phương Đường cong Elliptic Đường cong Elliptic - Dạng Weierstrass Nếu ta đặt Y = 2y + a1x + a3 a2 + 4a X = x + 1 2 12 thì ta có thể đưa phương trình (1) về dạng 2 3 Y = 4X + c4X + c6 Đơn giản hơn, ta có dạng Weierstrass của đường cong 2 3 y = x + a4x + a6 Khi đó biệt thức ∆ của đường cong là 3 2 ∆ = −16(4a4 + 27a6) Như vậy điều kiện để đường cong không kỳ dị (không có nghiệm bội): 3 2 4a4 + 27a6 6= 0 Chương 5: Đường cong Elliptic 39/45
  40. Các hàm số học Thặng dư bình phương Đường cong Elliptic Phép cộng trên đường cong Elliptic Hình: Phép cộng trên đường cong Elliptic. Chương 5: Đường cong Elliptic 40/45
  41. Các hàm số học Thặng dư bình phương Đường cong Elliptic Phép cộng trên đường cong Elliptic Với đường cong Elliptic dạng Weierstrass y2 = x3 + ax + b, ta có các công thức tính như sau: R = P + Q  2 yQ − yP xR = − xP − xQ xQ − xP   yQ − yP yR = −yP + (xP − xR) xQ − xP R = 2P = P + P  2 2 3xP + a xR = − 2xP 2yP  2  3xP + a yR = −yP + (xP − xR) 2yP Chương 5: Đường cong Elliptic 41/45
  42. Các hàm số học Thặng dư bình phương Đường cong Elliptic Đường cong Elliptic và các hệ mã hóa Định lý Cho E là một đường cong Elliptic trên trường hữu hạn Fq và P là một điểm trên đường cong. Khi đó có thể tính tọa độ của điểm kP bằng O(log k log3 q) phép tính bit. Ta dùng phương pháp nhân đôi liên tiếp để tính kP , chẳng hạn 205P = (2(2(2(2(2(2(2P + P ))) + P ) + P ))) + P gồm 7 phép nhân đôi một điểm và 4 phép cộng hai điểm. Như vậy, để tính kP từ k và P cho trước, ta cần thời gian đa thức. Giả sử B và P = kB các điểm của đường cong Elliptic E trên r trường hữu hạn Fq, q = p , p 6= 2, ta nói k là logarit cơ sở B của P . Bài toán tìm logarit của các điểm trên đường cong Elliptic đòi hỏi thời gian mũ, và không thể kết thúc trong khoảng thời gian chấp nhận được. Chương 5: Đường cong Elliptic 42/45
  43. Các hàm số học Thặng dư bình phương Đường cong Elliptic Mật mã khóa công khai Giả sử có một tập hợp n cá thể cần trao đổi thông tin mật với nhau: A1,A2, , An. Trước tiên ta chọn một đường cong Elliptic E trên trường hữu hạn Fq với một điểm B ∈ E làm cơ sở. q là một số đủ lớn, và tất cả thông tin trên đều được công khai. Sau đó, mỗi cá thể Aj chọn cho mình một khóa bí mật là một số nguyên ej nào đó. Khi đó, khóa công khai của các cá thể này là ejB. Giả sử Aj cần gửi thông báo mật là điểm Pm trên đường cong E cho Ai. Khi đó Aj sẽ chọn ngẫu nhiên một số nguyên s và gửi cho Ai cặp điểm (sB, Pm + s(eiB)). Khi nhận được cặp điểm này, Ai tiến hành giải mã bằng cách lấy điểm sau trừ đi ei lần điểm trước. Chương 5: Đường cong Elliptic 43/45
  44. Các hàm số học Thặng dư bình phương Đường cong Elliptic Mật mã tương tự mũ Chọn trước một đường cong Elliptic E trên trường hữu hạn Fq có N điểm và công khai các thông tin này. Người ta chứng minh được rằng với mọi điểm P thuộc đường cong E thì NP = 0. Mỗi cá thể Ai chọn cho mình một khóa bí mật ei là số nguyên nằm giữa 1 và N sao cho gcd(ei,N) = 1. Bằng thuật toán Euclide, Ai tìm được di thỏa mãn diei ≡ 1 (mod N). Giả sử Ai cần gửi một điểm Pm cho Aj, các bước được thực hiện như sau: Ai gửi cho Aj thông điệp eiPm. Aj gửi trả lại cho Ai thông điệp ej (eiPm). Ai gửi cho Aj thông điệp di(ej (eiPm)). Aj giải mã bằng cách tính dj (di(ej (eiPm))) = (1 + sN)Pm = Pm. Chương 5: Đường cong Elliptic 44/45
  45. Các hàm số học Thặng dư bình phương Đường cong Elliptic Ánh xạ số nguyên m thành điểm Pm trên (E): y2 = x3 + ax + b Với số k cho trước, xác suất để ta không tìm được điểm Pm không vượt quá 2−k. Giả sử số m nằm trong khoảng 1 ≤ m ≤ M. Ta chọn q = pr sao cho q > Mk. Ta tương ứng một số nguyên s ≤ q với một phần tử trong trường hữu hạn Fq như sau: r−1 X i s ←→ (c0, c1, , cr−1)p ←→ x = cit i=0 Ta lần lượt tìm các xj ứng với các số sj, trong đó sj = mk + j ≤ (m + 1)k ≤ Mk < q. 3 Với mỗi xj, ta tính Yj = xj + axj + b. Nếu tồn tại yj ∈ Fq sao 2 cho Yj = yj thì ta tương ứng m với Pm = (xj, yj). Chương 5: Đường cong Elliptic 45/45