Thuật toán Euclid mở rộng tìm phần tử nghịch đảo với mô-đun cho trước. Được sử dụng nhiều trong các bài toán mã hóa và giải mã các hệ mã hóa, đặc biệt là hệ mã hóa cổ điển.
Thuật toán:
Thuật toán Euclid mở rộng tìm phần tử nghịch đảo với mô-đun cho trước. Được sử dụng nhiều trong các bài toán mã hóa và giải mã các hệ mã hóa, đặc biệt là hệ mã hóa cổ điển.
var x, a, b, y: array; var i: integer; x[0] := m; x[1] := n; a[0] := 1; a[1] := 0; b[0] := 0; b[1] := 1; if [a = 1] then exit[1] else if [ucln[n,m] = 1] then exit[null] else begin I := 1; while [x[i] > 1] do begin
y[i] := x[i-1] div x[i];
i := i + 1;
x[i] := x[i-2] div x[i-1];
a[i] := a[i-2] – [a[i-1] * y[i-1]];
b[i] := b[i-2] – [b[i-1] * y[i-1]];
Thông tin: Mọi khó khăn hay phát sinh lỗi khi sửa dụng chương trình, mong mọi người liên hệ theo địa chỉ Email: tunghuynh.tn@gmail.com Cảm ơn đã sử dụng sản phẩm!.
Post navigation
Chú ý rằng đầu vào của thuật toán này phải là số nguyên không âm nhé! Ngoài ra, nếu bạn sử dụng Python 3.8 trở lên, bạn có thể import luôn hàm này từ module math:
from math import gcd
Cách tìm nghịch đảo modulo bằng Extended Euclidean Algorithm
Hàm trên đơn giản và dễ hiểu, nhưng nó chỉ tìm được ước chung lớn nhất. Để tìm được nghịch đảo modulo của một số, chúng ta cần một phiên bản nặng ký hơn, tên là Extended Euclidean Algorithm.
Với xx và yy nguyên tố cùng nhau [gcd[x,y]=1\gcd[x,y]=1], luôn tồn tại nghịch đảo x−1x^{-1} của xx modulo yy:
xx−1≡1mod yxx^{-1} \equiv 1 \mod y
Công thức trên tương đương với: tồn tại bb sao cho
x×x′+y×b=1x\times x' + y\times b= 1
Bài toán đó là kết quả thuật toán Extended Euclidean Algorithm: cho xx và yy, thuật toán sẽ tìm ra các giá trị a,b,ca,b,c sao cho
x×a+y×b=cx\times a + y\times b= c
với c=gcd[x,y]c=\gcd[x, y]. Bạn có thể thấy tại sao nó lại là phiên bản nâng cao rồi đó: ngoài việc tìm ra cc, nó còn lưu lại các trọng số liên quan. Nếu c=1c=1, chúng ta có thể thấy công thức đó giống công thức ở trên, nghĩa là aa sẽ là nghịch đảo của xx modulo yy; và tương tự bb sẽ là nghịch đảo của yy modulo xx.
Giải thích vậy nhiều rồi, chúng ta đi thẳng vào thuật toán nhé: điểm khác nhau của EEA so với phiên bản thông thường là ở mỗi bước, thuật toán này lưu các trọng số tương ứng với input sao cho tổng tuyến tính đó bằng giá trị modulo hiện tại. Có lẽ giải thích thế này hơi khó hiểu, nên ví dụ sẽ dễ hơn nhé:
Cho x=50x = 50 và y=21y=21. Ban đầu chúng ta có:
50=1×50+0×2121=0×50+1×21\begin{alignedat}{2} 50 =& 1\times 50 + 0 \times 21 \\ 21 =& 0\times 50 + 1 \times 21 \end{alignedat}
Tương tự với thuật toán Euclidean cơ bản, ta tìm số dư của xx chia yy, tuy nhiên bây giờ chúng ta phải keep track những trọng số trên: vì 50=21×2+850=21\times 2+8, chúng ta update công thức trên:
8=50−21×2=[1×50+0×21]−2×[0×50+1×21]=[1−2×0]×50+[0−2×1]×21=1×50−2×21\begin{alignedat}{2} 8 =& 50 - 21 \times 2 \\ =& [1\times 50 + 0 \times 21] - 2\times [0\times 50 + 1 \times 21] \\ =& [1 - 2\times 0]\times 50 + [0 - 2 \times 1] \times 21 \\ =& 1 \times 50 - 2\times 21 \end{alignedat}
Từ đó chúng ta update những giá trị cần lưu:
21=0×50+1×218=1×50−2×21\begin{alignedat}{2} 21 =& 0\times 50 + 1 \times 21 \\ 8 =& 1 \times 50 - 2\times 21 \end{alignedat}
Tiếp tục lấy modulo của 2 giá trị mới: do 21=8×2+521=8\times 2 + 5:
5=21−8×2=[0×50+1×21]−2×[1×50−2×21]=[0−2×1]×50+[1−2×−2]×21=−2×50+5×21\begin{alignedat}{2} 5 =& 21 - 8 \times 2 \\ =& [0\times 50 + 1 \times 21] - 2\times [1 \times 50 - 2\times 21] \\ =& [0 - 2\times 1]\times 50 + [1 - 2 \times -2] \times 21 \\ =& -2 \times 50 + 5\times 21 \end{alignedat}
Và update các trọng số:
8=1×50−2×215=−2×50+5×21\begin{alignedat}{2} 8 =& 1 \times 50 - 2\times 21 \\ 5 =& -2\times 50 + 5\times 21 \end{alignedat}
Cứ tương tự như vậy, qua các bước tiếp theo chúng ta có tiếp:
3=3×50+−7×212=−5×50+12×211=8×50−19×21\begin{alignedat}{2} 3 =& 3\times 50 + -7 \times 21 \\ 2 =& -5 \times 50 + 12\times 21 \\ 1 =& 8 \times 50 - 19\times 21 \end{alignedat}
Do 2%1=02\%1=0 nên thuật toán sẽ dừng ở đây. Từ kết quả này, chúng ta có:
- gcd[50,21]=1\gcd[50, 21] = 1
- 50−1mod 21=850^{-1} \mod 21 = 8
- 21−1mod 50=3121^{-1} \mod 50 = 31, do −19≡31mod 50-19 \equiv 31\mod 50.
Đơn giản, phải không? Từ đó ta viết thuật toán đầy đủ:
def eea[x, y]:
x_c1, x_c2 = 1, 0
y_c1, y_c2 = 0, 1
while True:
# get quotient and remainder
q, r = divmod[x, y]
# if found GCD, return
if r == 0:
return y_c1, y_c2, y
# else, keep track
x_c1, x_c2, y_c1, y_c2 = y_c1, y_c2, \
x_c1 - q * y_c1, x_c2 - q * c_2
x, y = y, r
Ngoài ra, nếu bạn dùng Python 3.8+, hàm có sẵn pow có thể được sử dụng để tính nghịch đảo modulo:
assert 8 == pow[50, -1, 21] and 31 == pow[21, -1, 50]
Vài điểm cần lưu ý khi dùng hàm builtin này:
- Đầu vào đều phải là các số nguyên có dạng
int - Không được import
powtừ modulemath. Tuy nhìn nhanh có vẻ giống nhau nhưngdef gcd[x, y]:while y: x, y = y, x % y return x
Bonus
Trong trường hợp bạn có các ước của modulo [ví dụ như nếu modulo là số nguyên tố, một trường hợp hay gặp phải], bạn có thể sử dụng định lý Fermat nhỏ để tìm nghịch đảo. Chúng ta có