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

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.

Tags:
  1. xo
    Tháng Mười Một 9, 2010 lúc 11:56 sáng

    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. Tháng Mười Một 9, 2010 lúc 7:16 chiều

    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. thksban
    Tháng Ba 15, 2012 lúc 2:34 sáng

    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. Tháng Ba 18, 2012 lúc 8:44 chiều

    Mình viết đoạn code trên để minh họa thôi chứ không dịch chạy thử.

  5. Khách
    Tháng Mười Hai 18, 2012 lúc 11:10 sáng

    Mình nghĩ cách làm này chưa chính xác.

  6. Đức ANh
    Tháng Năm 16, 2013 lúc 8:40 chiều

    Cái cột thứ 2 thấy vô dụng mà ??

  7. Khách
    Tháng Hai 20, 2014 lúc 3:22 chiều

    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

  8. Khách
    Tháng Sáu 1, 2014 lúc 12:59 chiều

    Thanks !

  9. Cường
    Tháng Mười 6, 2014 lúc 8:55 chiều

    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

  1. No trackbacks yet.

Gửi phản hồ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 Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: