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. 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;
    }
  2. 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

  3. 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

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s