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

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

Rate this post

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.

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 g0 = a, g1 = b
  • Lặp: gi+1 = gi-1 mod gi (gi+1 là số dư của gi-1 cho gi ) cho đến khi gk+1 = 0
  • Lúc đó: (a, b) = gk

Ta thấy ngay, theo thuật toán và nhận xét ở trên thì: (a, b) = (g0, g1) = (g1, g2) = … = (gk, gk+1) = (gk, 0) = gk. Thuật toán phải dừng vì dãy số nguyên không âm {gi} 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ố {gi},{ui},{vi} sao cho gi = ui * n + vi * a. “i và day {gi} giảm dần đến 1. Khi đó $k sao cho gk = 1 suy ra: 1 = uk * n + vk * a suy ra vk là nghịch  đảo  của  a  (vk  =  a-1  mod  n).  

Vấn  đề  bây  giờ  là  tìm  các  dãy{gi},{ui},{vi} 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 g0 = n, u0 = 1, v0 = 0 ta có: g0 = u0 * n + v0 * a
  • Với g1 = a, u1 = 0, v1 = 1 ta có: g1 = u1 * n + v1 * a

Tính: y = g0 div g1 (kết quả của phép chia nguyên g0 cho g1) Nhân đẳng thức thứ hai với y và trừ vào đẳng thức thứ nhất: g0 = u0 * n + v0 * a, g1 = u1 * n + v1 * a * y (g0 – y * g1) = (u0 – y * u1) * n + (v0 – y * v1) * a =>    g2 = u2 * n + v2 * a

Ta có thể thấy ngay là g2 = g0 mod g1

Làm tương tự, ta tính: y = g1 div g2

(g1 – y * g2) = (u1 – y * u2) * n + (v1 – y * v2) * a

=>   g3 = u3 * n + v3 * a

…………..

Ta thấy {gi} 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ó: gk+1 = 0, từ đó ta có gk = (a, n) = 1 => vk = 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:

g0 = n, u0 = 1, v0 = 0 g1 = a, u1 = 0, v1 = 1

Lặp:

  • y = gi-1 div gi
  • gi+1 = gi-1 – y * gi ui+1 = ui-1 – y * ui vi+1 = vi-1 – y * vi

Đến khi gk = 1

Ta có vk = a-1 mod n

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

iyguvĐẳng thức tương đương
032310323 = 1 * 323 + 0 * 299
129901299 = 0 * 323 + 1 * 299
21241-124 = 1 * 323 + -1 * 299
31211-121311 = -12 * 323 + 13 * 299
42225-272 = 25 * 323 + -27 * 299
551-1371481 = -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 vi không phụ thuộc vào kết quả ui do đó cột ui cũng có thể bỏ. Thuật toán còn lại:

Vgv
3230
2991
124-1
121113
22-27
51148

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:

g0 = n, v0 = 0 g1 = a, v1 = 1

Lặp:

y = gi-1 div gi

gi+1 = gi-1 – y ´ gi vi+1 = vi-1 – y ´ vi

Đến khi gk = 1

Ta có vk = 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ì: φ(pr) = pr * (p – 1)

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

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

Hoặc tính theo cách ở trên: φ(1000) = φ(23 * 53) = φ(23) * φ(53) = 22 *52 * 4 = 400.

  1. Định lý Fermat

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

  1. Đị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: an-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: an-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à x2 = 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 = 2kq 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) aq = 1 mod p

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

Leave a Reply