Bài giải thuật toán tìm số nghịch đảo bằng bảng
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 end;
while (b[i-1] < 0) do b[i-1] := b[i-1] + m;
exit(b[i-1]);
end;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: [email protected] Cảm ơn đã sử dụng sản phẩm!. Post navigationChú ý 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
Cách tìm nghịch đảo modulo bằng Extended Euclidean AlgorithmHà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ó:
Đơn giản, phải không? Từ đó ta viết thuật toán đầy đủ:
Ngoài ra, nếu bạn dùng Python 3.8+, hàm có sẵn
Vài điểm cần lưu ý khi dùng hàm builtin này:
BonusTrong 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ó |