zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:45

Báo xấu

102
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 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. Giả sử n = pr11 pr22 ...prkk . Khi đó k r +1 Y pj j − 1 σ(n) = j=1 pj − 1 k Y τ (n) = (rj + 1) j=1 Chương 3: Các hàm số học 7/45
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
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
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 Với m là một số nguyên dương, Mm = 2m − 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ố. M13 = 213 − 1 = 8191, mọi ước nguyên của M13 không vượt Xé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
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). Hệ quả. ai ≡ aj 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
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) ordn r Với u là một số nguyên dương, ta có ordn ru = . 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
Các hàm số học Thặng dư bình phương Đường cong Elliptic Định lý Lagrange Định lý (Lagrange) Giả sử f (x) = an xn + an−1 xn−1 + ... + a1 x + 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
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
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
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 Chứng minh rằng σk (n) = dk 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 Mp Mq = (2p − 1)(2q − 1) là số giả nguyên tố cơ sở 2. Chương 3: Các hàm số học 16/45
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
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
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
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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.