Chương 2 cung cấp cho người học cơ sở toán học của lý thuyết mật mã. Các nội dung chính được trình bày trong chương này gồm có: Số học các số nguyên và thuật toán Euclide, đồng dư theo modular, định lý số dư trung hoa, hệ hai phương trình đồng dư, lũy thừa modulo. . | Chương 2. Cơ sở toán học của lý thuyết mật mã Cho a, b≠0 là các số nguyên. Ta nói a chia hết cho b nếu tồn tại 1 số c sao cho: a= Ký hiệu b|a a là bội số của b (divisor), b là ước số của a ( mutiple) Ví dụ: 2| 6 Tính chia hết của số nguyên Số học các số nguyên và thuật toán Euclide Với a, b, c, d, e ∈Z, ta có: - Nếu a|b và b|c ⇒ a|c - Nếu a|b, thì ac|bc ∀c - Nếu c|a và c|b, thì c| da+ be ∀d, e - Nếu a|b và b≠0, thì |a|≤|b| - Nếu a|b và b|a, thì |a|=|b| Tính chia hết của các số nguyên Đối với mọi số n, d\{0}, luôn tồn tại duy nhất các số q, r∈Z sao cho: n=qd+r với 0=b Output: gcd(a, b). Trong khi b>=0 thực hiện: r a mod b a b b r Cho kết quả (a) Thuật toán Euclide tìm UCLN Thuật toán Euclid mở rộng dùng để tìm hai số x, y thỏa mãn phương trình sau: ax + by = gcd(a, b) Thuật toán Euclid mở rộng Euclide mở rộng Cho a=4864, b= 3458, tìm (d, x, y) Ví dụ (38, 32, -45) Số tự nhiên 11đều có thể viết dưới dạng: n=p1a1 .p2a2 pkak Lưu ý: số 1 không pải là ngto cũng không phải là hợp số. Nguyên tố và hợp số Hàm đếm các số nguyên tố(prime counting function) ∏(n) cho kết quả là các số nguyên tố nhỏ hơn hay | Chương 2. Cơ sở toán học của lý thuyết mật mã Cho a, b≠0 là các số nguyên. Ta nói a chia hết cho b nếu tồn tại 1 số c sao cho: a= Ký hiệu b|a a là bội số của b (divisor), b là ước số của a ( mutiple) Ví dụ: 2| 6 Tính chia hết của số nguyên Số học các số nguyên và thuật toán Euclide Với a, b, c, d, e ∈Z, ta có: - Nếu a|b và b|c ⇒ a|c - Nếu a|b, thì ac|bc ∀c - Nếu c|a và c|b, thì c| da+ be ∀d, e - Nếu a|b và b≠0, thì |a|≤|b| - Nếu a|b và b|a, thì |a|=|b| Tính chia hết của các số nguyên Đối với mọi số n, d\{0}, luôn tồn tại duy nhất các số q, r∈Z sao cho: n=qd+r với 0
