Bài toán tính nghịch đảo theo Modulo

Trước khi giải quyết bài toán nghịch đảo, chúng ta sẽ nhắc lại bài toán cổ điển của lý thuyết số là tìm ước số chung lớn nhất (ƯSCLN) hay great common divisor (gcd). Ước số chung lớn nhất của hai số a và b là số nguyên lớn nhất chia hết cả a và b.

Ta ký hiệu là ƯSCLN(a, b) hay gcd(a, b) hay  đơn giản là (a, b). Khi (a, b) = 1 thì a và b là 2 số nguyên tố cùng nhau. Thuật toán Euclid là một thuật toán cổ điển rất hiệu quả trong việc tìm ƯSCLN của 2 số. Ta sẽ nhắc lại thuật toán này.

Xem thêm V-model / V và V model/ Verification và Validation model

Thuật toán Euclid

Ý tưởng của thuật toán xuất phát từ phát biểu sau: Giả sử a >= b là hai số nguyên khác 0, nếu số d đồng thời chia hết a và b (d|a và d|b) và r là số dư của phép chia a cho b (r = a mod b) thì d|r.

Từ phát biểu này, có thể suy ra: gcd(a, b) = gcd(b, r). Ta thấy a >= b và b > r do đó bài toán tìm ƯSCLN của 2 số a và b đã chuyển thành bài toán tím ƯSCLN của hai số bé hơn là b và r.

Thuật toán Euclid tìm (a, b) như sau:

• Giả sử a ≥ b > 0 Đặt g₀ = a, g₁ = b
• Lặp: g_i+1 = g_i-1 mod g_i (g_i+1 là số dư của g_i-1 cho g_i ) cho đến khi g_k+1 = 0
• Lúc đó: (a, b) = g_k

Ta thấy ngay, theo thuật toán và nhận xét ở trên thì: (a, b) = (g₀, g₁) = (g₁, g₂) = … = (g_k, g_k+1) = (g_k, 0) = g_k. Thuật toán phải dừng vì dãy số nguyên không âm {g_i} với i > 0 là đơn điệu giảm bị chặn bởi 0 nên sẽ dừng tại giá trị 0.

Xem thêm Lý thuyết số học trong mã hóa

Ví dụ ta cần tính gcd(98, 56).

Ta có: (98, 56) = (56, 42) = (42,14) = (14, 0) = 14.

Ta sẽ áp dụng thuật toán Euclid để tìm nghịch đảo a^-1 mod n. Điều kiện cần thiết để tồn tại nghịch đảo như đã nói ở trên là (n, a) = 1.

Giả sử đã tìm các dãy số {g_i},{u_i},{v_i} sao cho g_i = u_i * n + v_i * a. “i và day {g_i} giảm dần đến 1. Khi đó $k sao cho g_k = 1 suy ra: 1 = u_k * n + v_k * a suy ra v_k là nghịch  đảo  của  a  (v_k  =  a^-1  mod  n).  

Vấn  đề  bây  giờ  là  tìm  các  dãy{g_i},{u_i},{v_i} như thế nào? Chúng ta sẽ thực hiện điều này bằng phương pháp xây dựng dần dần:

• Với g₀ = n, u₀ = 1, v₀ = 0 ta có: g₀ = u₀ * n + v₀ * a
• Với g₁ = a, u₁ = 0, v₁ = 1 ta có: g₁ = u₁ * n + v₁ * a

Tính: y = g₀ div g₁ (kết quả của phép chia nguyên g₀ cho g₁) Nhân đẳng thức thứ hai với y và trừ vào đẳng thức thứ nhất: g₀ = u₀ * n + v₀ * a, g₁ = u₁ * n + v₁ * a * y (g₀ – y * g₁) = (u₀ – y * u₁) * n + (v₀ – y * v₁) * a =>    g₂ = u₂ * n + v₂ * a

Ta có thể thấy ngay là g₂ = g₀ mod g₁

Làm tương tự, ta tính: y = g₁ div g₂

(g₁ – y * g₂) = (u₁ – y * u₂) * n + (v₁ – y * v₂) * a

=>   g₃ = u₃ * n + v₃ * a

…………..

Ta thấy {g_i} chính là dãy Euclid, do vậy, nếu cứ làm tiếp tục thì đến khi nào đó sẽ có: g_k+1 = 0, từ đó ta có g_k = (a, n) = 1 => v_k = a^-1(mod n).

Xem thêm Thuật toán mã hóa khối(block cipher)- AES

Thuật toán Euclid mở rộng

Tìm a^-1 mod n (điều kiện: (a, n) = 1, n > a > 0)

Đặt:

g₀ = n, u₀ = 1, v₀ = 0 g₁ = a, u₁ = 0, v₁ = 1

Lặp:

• y = g_i-1 div g_i
• g_i+1 = g_i-1 – y * g_i u_i+1 = u_i-1 – y * u_i v_i+1 = v_i-1 – y * v_i

Đến khi g_k = 1

Ta có v_k = a^-1 mod n

Để minh hoạ cho thuật toán Euclid, xét ví dụ: Tính 299^-1 mod 323.

i	y	g	u	v	Đẳng thức tương đương
0	–	323	1	0	323 = 1 * 323 + 0 * 299
1	–	299	0	1	299 = 0 * 323 + 1 * 299
2	1	24	1	-1	24 = 1 * 323 + -1 * 299
3	12	11	-12	13	11 = -12 * 323 + 13 * 299
4	2	2	25	-27	2 = 25 * 323 + -27 * 299
5	5	1	-137	148	1 = -137 * 323 + 148 * 299

Vậy: 299^-1 mod 323 = 148

Để tối ưu thuật toán, có thể bỏ ngay đi các cột i và “Đẳng thức tương đương”. Ngoài ra có thể nhận xét rằng việc tính v_i không phụ thuộc vào kết quả u_i do đó cột u_i cũng có thể bỏ. Thuật toán còn lại:

V	g	v
–	323	0
–	299	1
1	24	-1
12	11	13
2	2	-27
5	1	148

Tương ứng với mô tả thuật toán như sau:

Tìm a^-1 mod n (điều kiện: (a, n) = 1, n > a > 0) Đặt:

g₀ = n, v₀ = 0 g₁ = a, v₁ = 1

Lặp:

y = g_i-1 div g_i

g_i+1 = g_i-1 – y ´ g_i v_i+1 = v_i-1 – y ´ v_i

Đến khi g_k = 1

Ta có v_k = a^-1 mod n

Thuật toán còn có thể tối ưu nữa trong quá trình cài đặt nếu thay vì sử dụng cấu trúc mảng, chúng ta sẽ dùng các biến thường để tính toán.

Xem thêm Thuật toán mã hóa khối(block cipher) – DES

Bài toán tính nghịch đảo theo modulo có thể được thực hiện bằng các phương pháp khác nữa. Sau đây, chúng ta tiếp tục khảo sát thêm một phương pháp.

Ta gọi tập thặng dư đầy đủ (TTDĐĐ) theo mod n là tập tất cả các số từ 0 đến n-1: [0..n-1]. Tập thặng dư rút gọn (TTDRG) theo mod n bao gồm các số thuộc TTDĐĐ thoả điều kiện nguyên tố cùng nhau với n.

Ví dụ: Khi n = 10 thì TTDĐĐ(10) = {0,1,2,3,4,5,6,7,8,9}, TTDRG(10) = {1,3,7,9}.

Số phần tử của TTDRG được gọi là hàm phi Euler: φ(n). Như vậy φ(10) = 4. Có thể tính φ(n) theo sơ đồ sau:

• Bắt đầu từ tập n-1 số [1..n-1]
• Loại bỏ tất cả các ước số nguyên tố của n và tất cả các bội số của chúng
• Số các phần tử còn lại chính là φ(n)

Tuy nhiên, ta cũng có thể tính φ(n) dựa trên các khẳng định sau:

• Nếu p là số nguyên tố thì: φ(p) = p – 1;
• Nếu p là số nguyên tố thì: φ(p^r) = p^r * (p – 1)

̶   Nếu (a, b) = 1 thì: φ(a * b) = φ(a) * φ(b)

Ví dụ: φ(1000) = φ(2³ * 5³) = 1000 * (1-1/2) * (1-1/5) = 1000 * 2/5 = 400.

Hoặc tính theo cách ở trên: φ(1000) = φ(2³ * 5³) = φ(2³) * φ(5³) = 2² *5² * 4 = 400.

1. Định lý Fermat

Giả sử p là số nguyên tố và (a, p) = 1. Khi đó: a^p-1 = 1 mod p.

2. Định lý Euler

Với mọi số nguyên dương n và (a, n) = 1. Khi đó: a^φ(n) = 1 mod n.

Định lý Euler là trường hợp tổng quát của định lý Fermat. Trong định lý Euler, khi n là số nguyên tố thì ta sẽ nhận được định lý Fermat.

Xem thêm Mã hóa Stream Cipher

Bây giờ ta có vài cách tính nghịch đảo a^-1 mod n. Nếu đã biết φ(n) thì từ định lý Euler ta tìm được: a^-1 mod n = (a^-1 ´ a^φ(n)) mod n = a^{φ(n) -1} mod n. Đến đây, chúng ta có thể dùng thuật toán bình phương và nhân để rút gọn a^{φ(n) -1} mod n. Như vậy, để tính nghịch đảo theo modulo chúng ta có thể dùng các phương pháp: thử sai, thuật toán Euclid mở rộng hoặc dùng định lý Euler kết hợp với thuật toán bình phương và nhân. Trong ba cách đó thì cách đơn giản nhất là sử dụng thuật toán Euclid mở rộng.

Định lý Fermat có thể được sử dụng để tìm các số nguyên tố lớn. Để tạo các khoá mật mã người ta phải sử dụng các số nguyên tố lớn (khoảng trên 200 chữ số thập phân).

Kiểm tra một số có phải nguyên tố hay không là một vấn đề đơn giản đối với các số nhỏ nhưng không hề đơn giản và thường mất nhiều thời gian đối với các số lớn. Để giảm thiểu việc thử quá nhiều các số không phải là số nguyên tố, chúng ta sẽ sử dụng định lý Fermat để lọc ra những số có xác xuất là số nguyên tố cao để sử dụng.

Những số đó gọi là số “giả nguyên tố”. Ta biết rằng, nếu n là số nguyên tố và (a, n) = 1 thì theo định lý Fermat: a^n-1 = 1 mod n. Đây chỉ là điều kiện đủ để n là số nguyên tố mà không phải điều kiện cần. Tức là có thể có một vài số n không phải nguyên tố (hợp số) cũng thoả đẳng thức trên.

Nhưng nếu n thoả đẳng thức trên với một tập khá lớn các số a thì xác suất n là số nguyên tố sẽ khá cao. Còn tất nhiên, những số không thoả đẳng thức trên chắc chắn là hợp số nên có thể loại chúng khỏi danh sách thử. Ta thực hiện một thử nghiệm sau (Fermat test) để xác định số n có phải là giả nguyên tố hay không:

1. Chọn số lượng lớn (ví dụ 100) các số „a‟, 1 < a < n sao cho: (a, n) = 1
   • Kiểm tra: a^n-1 = 1 mod n ?
   • Nếu có một số a nào đó không thỏa điều 2. thì n là hợp số
   • Nếu 2. thỏa cho tất cả các giá trị a có thể kết luận gần đúng rằng n là số nguyên tố. Tức n là giả nguyên tố.

Bộ lọc Fermat khá đơn giản nhưng có nhiều trường hợp n là hợp số  mà nó không kiểm tra được với bộ khá lớn các số a. Do vậy trong thực tế, người ta hay sử dụng bộ lọc Miller – Rabin.

Xem thêm Tìm hiểu về mã hóa cổ điển

Đầu tiên chúng ta khảo sát một số tính chất của số nguyên tố:

Bổ đề 1.

Nếu p là số nguyên tố mà x² = 1 mod p thì hoặc x = 1 mod p hoặc x = (p-1) mod p.

Bổ đề 2.

Nếu p là số nguyên tố và p – 1 = 2^kq trong đó q là số lẻ và a là số nguyên thoả 1 < a < p – 1 thì một trong hai trường hợp sau sẽ xảy ra:

1) a^q = 1 mod p

2)     = (p-1) mod p với j là một giá trị nào đó (1     j     k)

Xem thêm Phân khối khóa (key) trong mã hóa