Chơng 1: Bổ túc về lý thuyết số 15 Với các đầu vo a = 4864 v b = 3458 Bởi vậy ta có: ƯCLN(4864,3458) = 38 v (4864)(32) + (3458)(-45) = 38. 1.3. Các số nguyên modulo n 1.3.1. Định nghĩa 1.9 Nếu a v b l các số nguyên thì a đợc gọi l đồng d với b theo modulo (ký hiệu l a = b mod n) nếu n (a b) . Số nguyên n đợc gọi l modulo đồng d. Ví dụ: 24 9 mod 5 vì 24 9 = 3.5 11 17 mod 7 vì 11 17 = 4.7 . 1.3.2. Các tính chất Đối với a, a1 , b, b1 , c ta có: (1) a b(mod n ) nếu v chỉ nếu a v b cũng có phần d khi chia cho n. (2) Tính phản xạ: a a(mod n ) . (3) Tính đối xứng: Nếu a b(mod n ) thì b a(mod n ) (4) Tính bắc cầu: Nếu a b(mod n ) v b c(mod n ) thì a c(mod n ) (5) Nếu a a1 (mod n ) v b b1 (mod n ) thì a + b a1 + b1 (mod n ) v a.b a1 .b1 (mod n ) Lớp tơng đơng của một số nguyên a l tập các số nguyên đồng d với a modulo n. Từ các tính chất (2), (3) v (5) ở trên ta có thể thấy rằng đối với n cố định, quan hệ đồng d theo modulo n sẽ phân hoạch Z thnh các lớp tơng đơng. 16 Giáo trình Mật mã học Nếu a = qn + r với 0 r n thì a r(mod n ) . Bởi vậy mỗi số nguyên a l đồng d theo modulo n với một số nguyên duy nhất nằm trong khoảng từ 0 tới n - 1, số ny đợc gọi l thặng d tối thiểu của a mod n. Nh vậy a v r có thể đợc dùng để biểu thị cho lớp tơng đơng ny. 1.3.3. Định nghĩa 1.10 Các số nguyên modulo n (ký hiệu Zn) l tập (các lớp tơng đơng) của các số nguyên {0,1, 2,K, n 1}. Các phép cộng, trừ, nhân trong Zn đợc thực hiện theo modulo n. Ví dụ: Z25 = {0,1,K, 24}. Trong Z 25 ta có: 13 + 16 = 4 vì 13 + 16 = 29 4 (mod 25 ) Tơng tự 13.16 = 8 trong Z25. 1.3.4. Định nghĩa 1.11 (Phần tử nghịch đảo) Cho a Z n , Phần tử nghịch đảo (ngợc theo phép nhân) của a mod n l một số nguyên x Z n sao cho: ax 1(mod n ) Nếu x tồn tại thì nó l duy nhất, a đợc gọi l khả nghịch. Phần tử nghịch đảo của a đợc ký hiệu l a1. 1.3.5. Định nghĩa 1.12 Phép chia của a cho b mod n l tích của a v b1 mod n tích ny đợc xác định nếu b l phần tử khả nghịch 1.3.6. Định lý 1.6 Cho a Z n , khi đó a l khả nghịch nếu v chỉ nếu: (a, n ) = 1 Ví dụ: Các phần tử khả nghịch trong Z9 l 1, 2, 3, 4, 5, 7 v 8. Chẳng hạn 4 1 = 7 vì 4 . 7 1 (mod 9 ) . Chơng 1: Bổ túc về lý thuyết số 17 1.3.7. Định lý 1.7 Cho d = (a,n). Phơng trình đồng d ax b(mod n ) có nghiệm x nếu v chỉ nếu d b , trong trờng hợp ny có đúng d nghiệm nằm giữa 0 v n - 1, những nghiệm ny l tất cả các đồng d theo modulo n d . 1.3.8. Định lý 1.8 (Phần d China) Nếu các số nguyên n1 , n 2 ,K, n k l nguyên tố cùng nhau từng đôi một thì hệ các phơng trình đồng d: x a 1 (mod n 1 ) x a 2 (mod n 2 ) .......... .......... .... x a k (mod n k ) sẽ có nghiệm duy nhất theo modulo n (n = n 1 . n 2 K n k ) . 1.3.9. Thuật toán Gausse Nghiệm x của hệ phơng trình đồng d trong định lý phần d China có thể đợc tính bằng: x= k a N M i i i mod n i =1 Trong đó: N i = n / n i v M i = N i 1 mod n i Các tính toán ny có thể đợc thực hiện trong 0 ( (lg n ) ) các 2 phép toán trên bit. Ví dụ: Cặp phơng trình đồng d x 3 (mod 7 ), x 7 (mod 13 ) có nghiệm duy nhất x 59 (mod 91 ) . 18 Giáo trình Mật mã học 1.3.10. Định lý 1.9 Nếu (n1 , n 2 ) = 1 thì cặp phơng trình đồng d. x a (mod n 1 ) , x a (mod n 2 ) có một nghiệm duy nhất x a (mod n 1 , n 2 ) . 1.3.11. Định nghĩa 1.13 Nhóm nhân của Z n l Z * = {a Z n (a, n ) = 1} n Đặc biệt, nếu n l số nguyên tố thì Z * = {a 1 a n 1}. n 1.3.12. Định nghĩa 1.14 Cấp của Z * l số các phần tử trong Z * (ký hiệu Z * ) n n n Theo định nghĩa của hm Phi-Euler ta thấy: Z * = (n ) n Cần để ý rằng nếu a Z * v b Z * thì a, b Z * v bởi vậy n n n Z * l đóng đối với phép nhân. n 1.3.13. Định lý 1.10 Cho p l một số nguyên tố: (1) Định lý Euler: Nếu a Z * thì a (n ) 1 (mod n ) . n (2) Nếu n l tích của các số nguyên khác nhau v nếu r s (mod (n )) thì a r as (mod n ) đối với mọi số nguyên a. Nói một cách khác khi lm việc với modulo n thì các số mũ có thể đợc rút gọn theo modulo (n ). Chơng 1: Bổ túc về lý thuyết số 19 1.3.14. Định lý 1.11 Cho p l một số nguyên tố: (1) Định lý Ferma: Nếu (a, p) = 1 thì a p 1 1 (mod p ) . (2) Nếu r s (mod p 1 ) thì a r a s (mod p ) đối với mọi số nguyên a. Nói một cách khác khi lm việc với modulo của một số nguyên tố p thì các luỹ thừa có thể đợc rút gọn theo modulo p - 1. (3) Đặc biệt a p a (mod p ) với mọi số nguyên a. 1.3.15. Định nghĩa 1.15 Cho a Z * . Cấp của a (ký hiệu l ord(a ) ) l số nguyên dơng n nhỏ nhất t sao cho a t 1 (mod n ) . 1.3.16. Định nghĩa 1.16 Cho a Z * , ord(a ) = t v a s 1 (mod n ) khi đó t l ớc của n s. Đặc biệt t (n ) . Ví dụ: Cho n = 21, khi đó Z * = {1, 2, 4 , 5, 8 , 10 , 11 , 13 , 16 , 17 , 19 , 20 } 21 Chú ý rằng (21 ) = (7 ) (3 ) = 12 = Z * . Cấp của các 21 phần tử trong Z * đợc nêu trong bảng sau: 21 Bảng 13: Cấp của các phần tử trong Z * 21 * a Z 21 1 2 4 5 8 10 11 13 16 17 19 20 Ord(a) 1 6 3 6 2 6 6 2 3 6 6 2 20 Giáo trình Mật mã học 1.3.17. Định nghĩa 1.17 Cho Z * . Nếu cấp của l (n ) thì đợc gọi l phần n tử sinh hay phần tử nguyên thủy của Z * . Nếu Z * có một phần tử n n sinh thì Z * đợc gọi l cyclic. n 1.3.18. Các tính chất của các phần tử sinh của (1) Z* n Z* n có phần tử sinh nếu v chỉ nếu n = 2, 4, p k hoặc l 2p k , trong đó p l một số nguyên tố lẻ v k 1 . Đặc biệt, nếu p l * một số nguyên tố thì Z n có phần tử sinh. * (2) Nếu l một phần tử sinh của Z n thì: Z * = { i mod n 0 i (n ) 1 } n (3) Giả sử rằng l một phần tử sinh của b = i mod n cũng l một phần tử sinh của (i, (n )) = 1 . Từ đó ta rút ra rằng nếu Z* n tử sinh l ((n )) . Z* n Z* , n khi đó nếu v chỉ nếu l cyclic thì số các phần (4) Zn l một phần tử sinh của Z n nếu v chỉ nếu * * (n ) / p 1(mod n ) đối với mỗi nguyên tố p của (n ) . Ví dụ: Z* 21 không l cyclic vì nó không chứa một phần tử có cấp (21) = 12 (Chú ý rằng 21 không thỏa mãn điều kiện (1) ở trên). Z * l cyclic v có một phần tử sinh = 2 . 25