Tài liệu Kỹ thuật lập trình - Chương 2: Giới thiệu lý thuyết số

Trong chương này sẽ trình bày ngắn gọn những kiến thức cơ bản về lý thuyết số, nó là công cụ hữu ích để hiểu sâu một thuật toán mật mã nào đó.
Nội dung trích xuất từ tài liệu:
Tài liệu Kỹ thuật lập trình - Chương 2: Giới thiệu lý thuyết số CHƯƠNG 2 GIỚI THIỆU VỀ LÝ THUYẾT SỐ Hầu hết các thuật toán mật mã khóa công khai được xây dựng dựa trên các khái ni ệm c ủa lýthuyết số. Trong chương này sẽ trình bày ngắn gọn những kiến thức cơ b ản v ề lý thuy ết s ố, nó làcông cụ hữu ích để hiểu sâu một thuật toán mật mã nào đó.2.1 Các số nguyên tố và các số nguyên tố cùng nhau2.1.1 Các ước số Nói rằng, b (một số khác 0) là ước số của a nếu a = mb, với một giá trị m nào đó, ở đây a, b, m làcác số nguyên. Như vậy, b là ước số của a, nếu như chia a cho b không còn lại số dư. Để kí hiệu b làước số của a thường sử dụng cách viết ba. Có các quan hệ sau: o Nếu a1, thì a = ± 1. o Nếu ba và ab, thì a = ± b. o Số b bất kỳ khác 0 là ước số của 0. o Nếu bg và bh, thì b(mg + nh) đối với bất kì số nguyên m, n. Để chứng minh khẳng định cuối cùng, cần chú ý như sau: nếu bg thì g có dạng g = b * g1, đối với số nguyên g1 nào đó, nếu bh thì h có dạng h = b * h1, đối với giá trị nguyên h1 nào đó, Vì vậy: mg + nh = mbg1 + nbh1 = b * (mg1+ nh1) Cuối cùng, b là ước số của mg + nh. Ví dụ 2.1: Các số 1, 2, 3, 4, 6, 8, 12 và 24 là các ước số của 24. Ví dụ 2.2: b = 7, g = 14, h = 63, m = 3, n = 2 714 và 763. Yêu cầu chứng minh rằng 7(3 * 14 + 2 * 63). Chúng ta có: ( 3 * 14 + 2 * 63 ) = 7(3 * 2 + 2 * 9) Như vậy, rõ ràng rằng 77(3 * 2 + 2 * 9).2.1.2 Các số nguyên tố Một số nguyên p > 1 được gọi là số nguyên tố, nếu chỉ có ± 1 và ± p là ước số của nó. Một số nguyên bất kỳ a > 1 có thể phân tích thành các thừa số và được trình bày dưới dạng: a = p1 1 p2 2 ... ptαt , α α ở đây: p1 < p2 < … < pt là các số nguyên tố, còn các giá trị αi > 0. Ví dụ 2.3: 91 = 7 * 13; 11011 = 7 * 112 * 13. Nếu P là kí hiệu tập hợp tất cả các số nguyên tố, thì đối với m ột s ố nguyên d ương b ất kì đ ượcviết duy nhất dưới dạng: a a = ∏ p p, ở đây tất cả các ap ≥ 0 P 1 Trong công thức này, biểu thức ở vế phải sau dấu bằng, ký hiệu tích theo t ất cả khả năng của cácsố nguyên tố p. Đối với mỗi giá trị cụ thể của a thì giá trị lớn nhất của chỉ số ap sẽ bằng 0. Ví dụ 2.4: 3600 = 24 * 32 * 52. Các giá trị của một số nguyên dương bất kỳ có thể liệt kê dưới một dạng đơn giản của t ất cả cácchỉ số khác không theo công thức ở trên. Ví dụ 2.5: Số nguyên 12 có thể trình bày như {a2 = 2, a3 = 1}. Số nguyên 18 có thể trình bày như {a2 = 1, a3 = 2}. Phép nhân hai số nguyên tương đương với phép cộng các giá trị các chỉ số phù hợp: k = m * n → kp = mp + np, đối với tất cả các p. Ví dụ 2.6: k = 12 * 18 = 216, k2 = 2 + 1 = 3, k3 = 1 + 2 = 3, 216 = 23 * 33 Bổ đề: Một số nguyên dương bất kì dạng pk chỉ có thể chia hết cho một số nguyên, khi số bị chiacó bậc của số nguyên tố p với chỉ số không vượt hơn k, nghĩa là số pj với j ≤ k. Như vậy: ab → ap ≤ bp, đối với tất cả p. Ví dụ 2.7: a = 12 , b = 36 , 1236, 12 = 22 * 3, 36 = 22 * 32 a2 = 2 = b2, a3 = 1 ≤ 2 = b3.2.1.3 Các số nguyên tố cùng nhau Chúng ta sẽ sử dụng ký hiệu gcd( a, b) để chỉ ước số chung lớn nhất (UCLN) của số a và b. Nóirằng, một số nguyên dương c là UCLN của a và b, nếu: o c là ước số của a và b. o Ước số bất kỳ của a và b đều là ước số của c. Có thể định nghĩa tương đương như sau: gcd(a, b) = max [k, khi ka và kb]. Bởi vì, đòi hỏi rằng UCLN là một số dương, chúng ta có gcd( a, b) = gcd(a, –b ) = gcd(–a, b) =gcd(–a, –b ). Nói chung, gcd(a, b) = gcd(|a|, |b|). Ví dụ 2.8: gcd(60, 24 ) = gcd(60, –24 ) = 12. Bởi vì tất cả các số nguyên khác không đều là ước số của số 0, chúng ta luôn luôn có: gcd( a, 0 ) = |a|. Dễ dàng xác định được UCLN của hai số nguyên dương, nếu các số này được trình bày dưới dạngtích của các thừa số nguyên tố. Ví dụ 2.9: 300 = 22 * 31 * 52, 18 = 21 * 32. gcd(18, 300) = 21 × 31 × 50 = 6. 2 Trong trường hợp chung: k = gcd(a, b) → kp = min (ap, bp), đối với tất cả các p. Việc xác định các thừa số nguyên tố của các số lớn là bài toán không đ ơn gi ản, b ởi vì r ằng cáctrình bày ở trên không cho một khả năng thực tiễn để tính UCLN của hai số. Các số nguyên a và b là nguyên tố cùng nhau, nếu chúng không có ước số nguyên t ố chung, hayước số chung ...