Tìm nghịch đảo theo phép đồng dư

Mình thật có duyên với cái thuật toán Euclide mở rộng để tìm nghịch đảo theo phép đồng dư và giải phương trình Diophantus tuyến tính này. Cứ mỗi lần trước khi thi cử là lại vác quyển Số học ra để gạo nó, mà gạo từ năm lớp 8 đến 12 vẫn không thuộc. Và bây giờ đến năm thứ tư vẫn lại phải gạo nó T_T.

Vào chủ đề chính. Tình hình là vừa mới kiếm được cách tìm nghịch đảo theo phép đồng dư để chuẩn bị thi mật mã. Mà môn này mình thì cúp, còn hai đồng minh chiến lược thì ngủ, và khả năng là có một số anh em khác vừa ngủ vừa cúp, nên tranh thủ post lại cách giải lên đây.

Cách giải này tìm thấy trong chính quyển sách giáo khoa Cryptography and Network Security Principles and Practices 🙂 (đừng đọc Wiki). Ta giả vờ nghiên cứu thuật toán đã.

Tìm nghịch đảo của b (tức là b-1) modulo m. Bắt buộc đưa về 0 < b < m.

EXTENDED EUCLID(m, b)
1. (A1, A2, A3) (1, 0, m); (B1, B2, B3) (0, 1, b)
2. if B3 = 0 return A3 = gcd(m, b); no inverse
3. if B3 = 1 return B3 = gcd(m, b); B2 = b1 mod m
4. Q = thương của A3 / B3.
5. (T1, T2, T3) <- (A1 – QB1, A2 – QB2, A3 – QB3)
6. (A1, A2, A3) <- (B1, B2, B3)
7. (B1, B2, B3) <- (T1, T2, T3)
8. goto 2

Ta luôn có mT1 + bT2 = T3 mA1 + bA2 = A3 mB1 + bB2 = B3.

Tất nhiên sinh viên BK làm gì có thời gian mà đọc cái này. Ta ví dụ luôn với b = 550, m = 1759 như sách giáo khoa, nhưng mình sửa lại cách kẻ bảng chút ít cho nó nhanh hơn :”>.

Hàng đầu là 1, 0, m. Hàng hai là 0, 1, b. Chú ý hàng đầu là m. Và nhắc lại, bắt buộc đưa về 0 < b < m.

Q 1 0 1759
  0 1 550

Lấy hàng trên cột cuối chi hàng dưới cột cuối, tức là 1759 / 550. Thương là Q.

Q 1 0 1759
3 0 1 550

Lấy Q nhân với hàng dưới (tức là 3 nhân với các số cùng hàng), rồi lấy hàng trên trừ đi kết quả, cột theo cột, được hàng tiếp.

Q 1 0 1759
3 0 1 550
  1 -3 109

Và lại tính Q = 550 / 109. Làm thế cho đến khi số ở cột cuối là 1.

Q 1 0 1759
3 0 1 550
5 1 -3 109
21 -5 16 5
1 106 -339 4
  -111 355 1

Và số cạnh số 1 đó (số 355) là nghịch đảo của 550 modulo 1759, hay 355 * 550 = 1 (mod 1759).

Tất nhiên nếu bạn chưa gặp số 1 mà đã gặp 0 rồi thì tức là không có nghịch đảo.

Q 1 0 15
1 0 1 12
4 1 -1 3
  -4 5 0

Khi đó số trên số 0 là ước chung lớn nhất (tức là 3), và hai số cùng hàng với 3 là 1 và –1 có tính chất 15 * 1 + 12 * (-1) = 3.

Trường hợp 1759 mà làm tiếp thì cũng sẽ gặp 0, có điều việc làm tiếp là không cần thiết. Dĩ nhiên 1759 * (-111) + 550 * 355 = 1.

Advertisements

9 thoughts on “Tìm nghịch đảo theo phép đồng dư

  1. cho minh hoi la ban co code cua chuong trinh tim so nghich dao nay khong. Cho minh xin voi ( neu bang C thi cang tot ). Minh cam on nhieu nha!

  2. Nhận vào m và b, in ra nghịch đảo. Nếu in ra 0 thì là không có nghịch đảo.

    #include<stdio.h>
    
    
    int inverse(int m, int b) {
        int a1 = 1, a2 = 0, a3 = m;
        int b1 = 0, b2 = 1, b3 = b;
        int q;
        int t1, t2, t3;
        while (1) {
            if (b3 == 0) return 0;
            if (b3 == 1) return b2;
            int q = a3 / b3;
            t1 = a1 - q * b1; t2 = a2 - q * b2; t3 = a3 - q * b3;
            a1 = b1; a2 = b2; a3 = b3;
            b1 = t1; b2 = t2; b3 = t3;
        }
    }
    
    
    int main(int argc, char *argv[]) {
        int m = atoi(argv[1]);
        int b = atoi(argv[2]);
        printf("%d", inverse(m, b));
        return 0;
    }
  3. Chưa đúng lắm bạn, bạn có test với số khác không, b và m là những số khác liệu có đúng k?

  4. cách làm sai thì phải nếu tìm số nghịch đảo của 7 với m=26 và tìm số nghịch đảo của 11 cũng với m=26 thì nhận thấy làm theo cách trên không cho ra kết quả đúng. Vậy là bạn bạn làm như thế kết quả là bao nhiêu

  5. Hay quá.cảm ơn anh nhiều.em đang trăn trở với nó đây. mấy hôm đi học toàn đến muộn.hỏi mấy đứa cũng k hiểu cách trong sách.e trăn trở mấy ngày đấy.vừa hay lại còn nhanh gấp vài lần như làm theo sách

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s