Chương 1. CÁC KIẾN THỨC CƠ SỞ Lý thuyết mật mã là một ngành khoa học đƣợc xây dựng dựa trên cơ sở toán học, đặc biệt là lý thuyết số học. Chƣơng này tổng hợp một số kiến thức toán học liên quan đƣợc sử dụng trong lý thuyết mật mã cũng nhƣ trong lĩnh vực chữ ký số [2, 3, 5, 7, 33]. LÝ THUYẾT SỐ HỌC 1.
Phép chia hết và chia có dƣ 1.1 1) Cho hai số nguyên a và b (b ≠ 0). Nếu có một số nguyên q sao cho a = b.q thì ta nói rằng a chia hết cho b, kí hiệu b\a. Khi đó ta nói b là ƣớc của a hay a là bội của b.4 do đó 2 là ƣớc của 8 và ký hiệu 2\8. 2) Cho các số nguyên a, b (b ≠ 0), tồn tại cặp số nguyên (q, r) duy nhất sao cho a = b.q + r, 0 r < b , khi đó q gọi là thƣơng nguyên, r gọi là số dƣ của phép chia a cho b.
Nếu r = 0 thì ta có phép chia hết. Một số tính chất Với a, b, c là các số nguyên ta có: 1) ±1\a, với mọi a; a\0, a\a, với mọi a ≠ 0. 2) Nếu a\b và b\c thì a\c, với mọi a ≠ 0, b ≠ 0. 4) Nếu a\b và a\c thì a\(b+c) và a\(b-c), với mọi a ≠ 0.
5) Nếu a\b và c\d thì a. TIEU LUAN MOI download : skknchat@gmail. Ƣớc chung lớn nhất, bội chung nhỏ nhất 1.2 1) Một số nguyên d đƣợc gọi là ƣớc chung của các số nguyên a 1, a2, …, an nếu nó là ƣớc của tất cả các số đó. 2) Một số nguyên m đƣợc gọi là bội chung của các số nguyên a1, a2, …, an nếu nó là bội của tất cả các số đó.
3) Một ƣớc chung d>0 của các số nguyên a1, a2, …, an sao cho mọi ƣớc chung của a1, a2, …, an đều là ƣớc của d, thì d đƣợc goi là ƣớc chung lớn nhất của a1, a2, …, an và ký hiệu là d = gcd(a1, a2, …, an). Để cho gọn trong trình bày ta có thể ký hiệu là d = (a1, a2, …, an). 4) Nếu gcd(a1, a2, …, an) = 1 thì các số a1, a2, …, an đƣợc gọi là nguyên tố cùng nhau. 5) Một bội chung m>0 của các số nguyên a1, a2, …, an sao cho mọi bội chung của a1, a2, …, an đều là bội của m, thì m đƣợc goi là bội chung nhỏ nhất của a1, a2, …, an và ký hiệu là m = lcm(a1, a2, …, an).
Ví dụ: gcd(12,18) = 6; lcm(12,18) = 36; gcd(8,9) = 1 do đó 8 và 9 là hai số nguyên tố cùng nhau. Tính chất 1) d = gcd(a1, a2, …, an) khi và chỉ khi tồn tại các số x1, x2,…, xn sao cho: d = a1x1+a2x2+…+an. 3) Nếu d là một ƣớc chung của a1, a2, …, an thì: d = gcd(a1, a2, …, an) khi và chỉ khi gcd(a1/d, a2/d,…, an/d) =1. 4) Nếu gcd(a,b) = 1 và b\ac thì b\c.
TIEU LUAN MOI download : skknchat@gmail.dung 5) Nếu gcd(a,b) = 1 thì gcd(ac,b) = gcd(c,b). 6) Nếu gcd(a, b) =1 thì lcm(a, b) = ab. 7) Nếu b > 0, a = bq+r thì gcd(a,b) = gcd(b,r). Thuật toán Euclide tìm ước chung lớn nhất 1) Bài toán Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b.
Kết quả: gcd(a,b).2 + 0 TIEU LUAN MOI download : skknchat@gmail. Thuật toán Euclide mở rộng 1) Bài toán Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b. Kết quả: d = gcd(a,b) và hai số x, y sao cho: ax + by = d.