Kiến thức

Extended Euclidean Algorithm: cách tính ước chung lớn nhất và nghịch đảo modulo

Bạn đang xem: Extended Euclidean Algorithm: cách tính ước chung lớn nhất và nghịch đảo modulo

Extended Euclidean Algorithm: cách tính ước chung lớn nhất và nghịch đảo modulo

May Fest

  • Report

Đây là một bài trong series

Algorithms

.

Xem thêm: Topping Là Gì? Các Loại Topping Trà Sữa

Mở bài

Chào mừng các bạn đến với bài tiếp theo trong series các thuật toán 😄 Thuật toán này được sử dụng khá nhiều trong cả competitive programming lẫn cryptography, nên các bạn có đam mê chơi Viblo Code hay CTF đều nên đọc nhé!

Không chần chừ gì nữa, chúng ta vào bài thôi!

Cách tìm ước chung lớn nhất bằng Euclidean Algorithm

Với g=gcd⁡(x,y)g=gcd(x,y), chúng ta có g∣xg|xg∣yg|y. Điều đó dẫn tới g∣x−yg|x-y, và chúng ta có một thuật toán cơ bản (nhưng chậm):

def gcd_naive(x, y): while True: if x < y: x, y = y, x if y == 0: return x x, y = x - y, y 

Để ý rằng chúng ta đang trừ yy khỏi xx cho đến lúc x<yx < y – phép toán này tương đương với việc tìm số dư của xx chia yy. Từ đó, chúng ta có được thuật toán Euclidean để tìm GCD:

def gcd(x, y): while y: x, y = y, x % y return x 

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 

Xem thêm: Ngũ Hành Tương Khắc Tương Sinh Là Gì? Và Ứng Dụng Trong Cuộc Sống

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 xxyy nguyên tố cùng nhau (gcd⁡(x,y)=1gcd(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=1xtimes x’ + ytimes b= 1

Bài toán đó là kết quả thuật toán Extended Euclidean Algorithm: cho xxyy, thuật toán sẽ tìm ra các giá trị a,b,ca,b,c sao cho

x×a+y×b=cxtimes a + ytimes 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 = 50y=21y=21. Ban đầu chúng ta có:

50=1×50+0×2121=0×50+1×21begin{alignedat}{2} 50 =& 1times 50 + 0 times 21 \ 21 =& 0times 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=21times 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×21begin{alignedat}{2} 8 =& 50 – 21 times 2 \ =& (1times 50 + 0 times 21) – 2times (0times 50 + 1 times 21) \ =& (1 – 2times 0)times 50 + (0 – 2 times 1) times 21 \ =& 1 times 50 – 2times 21 end{alignedat}

Từ đó chúng ta update những giá trị cần lưu:

21=0×50+1×218=1×50−2×21begin{alignedat}{2} 21 =& 0times 50 + 1 times 21 \ 8 =& 1 times 50 – 2times 21 end{alignedat}

Tiếp tục lấy modulo của 2 giá trị mới: do 21=8×2+521=8times 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×21begin{alignedat}{2} 5 =& 21 – 8 times 2 \ =& (0times 50 + 1 times 21) – 2times (1 times 50 – 2times 21) \ =& (0 – 2times 1)times 50 + (1 – 2 times -2) times 21 \ =& -2 times 50 + 5times 21 end{alignedat}

Và update các trọng số:

8=1×50−2×215=−2×50+5×21begin{alignedat}{2} 8 =& 1 times 50 – 2times 21 \ 5 =& -2times 50 + 5times 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×21begin{alignedat}{2} 3 =& 3times 50 + -7 times 21 \ 2 =& -5 times 50 + 12times 21 \ 1 =& 8 times 50 – 19times 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)=1gcd(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 31mod 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 pow từ module math. Tuy nhìn nhanh có vẻ giống nhau nhưng math.pow không hỗ trợ gì các phép toán mũ số nguyên trong modulo cả.

Xem thêm: Joule’i-Lenzi seadus – Vikipeedia

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ó

xφ(n)≡1mod  nx^varphi(n)equiv 1mod n

Từ đó, đơn giản chúng ta tìm nghịch đảo bằng cách

xφ(n)−1≡x−1mod  nx^{varphi(n)-1}equiv x^{-1}mod n

Trong đó,

Euler’s phi

có thể tính theo công thức sau: nếu nn có phân tích thừa số nguyên tố là

n=Πipiein = Pi_ip_ie^i

thì

φ(n)=Πi(pi−1)piei−1varphi(n)=Pi_i(p_i-1)p_i^{e_i-1}

Còn để tính nhanh mũ thì chúng ta có thể sử dụng phương pháp

exponentiation-by-squaring

nhé 😃

Kết bài

Có vẻ như Python 3.8+ đã giải quyết hết các vấn đề rồi nhỉ? 😦 Với những phiên bản/ngôn ngữ lập trình khác, bạn có thể theo hướng dẫn này để tự viết một hàm EEA cho riêng mình nhé! Good luck, and have fun 😎

Extended Euclidean Algorithm

multiplicative inverse

Algorithm

gcd

All Rights Reserved

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Check Also
Close
Back to top button