Lý thuyết số là một ngành của toán học đã tồn tại và có lịch sử từ rất lâu đời. Lý thuyết số chủ yếu nghiên cứu về các con số và tính chất của chúng, đặc biệt là các số nguyên. Lý thuyết số tồn tại song song với mật mã học và dường như chúng không có nhiều mối quan hệ với nhau.
Đến nửa cuối thế kỷ 20, nhiều nghiên cứu khác nhau đã cho thấy mối quan hệ mật thiết giữa lý thuyết số và mật mã học. Nhiều thuật toán mã hoá khoá công khai xây dựng vào thập niên 70 của thế kỷ trước hoàn toàn dựa trên cơ sở lý thuyết số. Sau này các thuật toán mã hoá khối khác cũng xây dựng dựa trên nền tảng của lý thuyết số.
Và ngày nay, mối quan hệ giữa mật mã hiện đại và lý thuyết số là không thể tách rời. Trong chương này, chúng ta sẽ khảo sát một số khái niệm và thuật toán của lý thuyết số, làm cơ sở nền tảng trong xây dựng các thuật toán mật mã hiện đại sẽ được khảo sát ở các chương sau như: RSA, AES,…
Lý thuyết số chủ yếu làm việc trên tập các số nguyên rời rạc. Các phép tính sử dụng nhiều trong lý thuyết số là phép cộng và phép nhân. Các phép tính khác như trừ, chia hay luỹ thừa được suy ra từ hai phép tính cơ bản trên. Nếu không có chú thích gì đặc biệt thì khi nói là các số ta sẽ hiểu là các số nguyên. Trước tiên, chúng ta sẽ ôn lại một số kiến thức cơ bản.
Các bài viết liên quan:
Một số khái niệm cơ bản trong lý thuyết số
- Ta nói số b # 0 chia hết số a nếu tồn tại số m sao cho: a = m * b.
Ký hiệu: b|a và nói b là ước số của a. Khi đó ta nói, a chia hết cho b hay a là bội số của b.
Ví dụ: các số 1, 2, 3, 4, 6, 8, 12, 24 chia hết 24 và là ước số của 24.
- Số nguyên tố là số mà chỉ có hai ước số: 1 và chính nó.
Ví dụ các số nguyên tố: 1 (là số nguyên tố đặc biệt), 2, 3, 5, 7,…Tương tự, các đa thức có khái niệm tối giản. Đa thức với hệ số nguyên x2 + x = x (x + 1) là không tối giản vì có thể phân tích thành tích của hai đa thức nguyên với bậc nhỏ hơn. Còn đa thức x3 + x + 1 là tối giản vì nó không thể phân tích thành tích của hai đa thức nguyên khác.
- Phân tích một số là viết triển khai số đó dưới dạng tích của các số khác: 48 = 4 * 6 * 2.
Ta thấy việc phân tích một số khó khăn hơn nhiều so với việc nhân các số tìm được với nhau.
Khi tất cả các số thành phần là nguyên tố, ta gọi đó là phân tích một số ra thừa số nguyên tố (phân tích nguyên tố), ví dụ: 48 = 2 * 2 * 2 * 2 * 3 = 24 * 3.
- Hai số gọi là nguyên tố cùng nhau nếu chúng không có ước số chung nào khác ngoài số 1. Ví dụ 48 và 25 là nguyên tố cùng nhau và ký hiệu: (48, 25) = 1.
- Hai số a và b gọi là đồng dư (congruence) theo modulo n và ký hiệu a = b mod n, (n > 0) nếu phép chia a và b cho n có cùng số dư.
Ví dụ: 100 = 34 mod 11.
Nếu 0 <= b <= n – 1 thì b là thặng dư (residue) của a theo mod n.
Ví dụ: -12 mod 7 = -5 mod 7 = 2 mod 7 = 9 mod 7. Các số -12, -5, 2, 9, là đồng dư theo mod 7 nhưng chỉ có giá trị 2 được gọi là thặng dư vì 0 <= 2 <= 7-1.
- Phép tính modulo. Nếu tính theo modulo n thì kết quả sẽ thuộc [0, n-1].
Các phép tính cộng: (a + b) mod n; Trừ: (a – b) mod n; Nhân: (a * b) mod n đều được thực hiện theo trình tự như các phép tính số học bình thường nhưng sau đó kết quả phải rút gọn theo mod n và sẽ nằm trong khoảng [0, n-1].
Các phép tính này thực hiện dễ dàng vì kết quả của chúng luôn nằm trong tập các số nguyên.
- Phép tính nghịch đảo: số nguyên b-1 là nghịch đảo của b nếu b ´ b-1 = 1 mod n.
Ví dụ: 2 là nghịch đảo của 3 theo mod 5 vì 2 * 3 = 1 mod 5. Lúc đó ta ký hiệu: 2-1 = 3 mod 5. Tất nhiên cũng có: 3-1 = 2 mod 5.
Giá trị nghịch đảo không phải lúc nào cũng tồn tại. Ví dụ: không tồn tại 4-1 mod 6. Thật vậy, giả sử tồn tại số m = 4-1 mod 6.
Khi đó theo định nghĩa: 4m = 1 mod 6 hay tồn tại số nguyên k sao cho 4m = 6k + 1. Điều này không thể xảy ra vì vế trái là số chẵn còn vế phải là số lẻ. Vậy thì khi nào nghịch đảo tồn tại? Người ta đã chứng minh được rằng điều kiện cần và đủ để tồn tại nghịch đảo a-1 mod n là a và n phải là hai số nguyên tố cùng nhau: (a, n) = 1.
- Từ khái niệm số nghịch đảo chúng ta sẽ định nghĩa phép chia theo modulo. Khi tính: (a / b) mod n, nếu b|a thì tính bình thường. Trường hợp ngược lại, ta sẽ định nghĩa:
(a / b) mod n = (a * b-1) mod n. Ví dụ: 7/2 = (7 * 2-1 ) mod 5 = 7 * 3 = 21 mod 5 = 1.
