Cách tính toán "nghịch đảo nhân mô-đun" khi mẫu số không đồng nhất với m?

Question

tôi cần phải tính toán (a/b) mod m nơi a và b là những con số rất lớn.

Những gì tôi đang cố gắng làm là để tính toán (a mod m) * (x mod m), nơi x là modular inverse của b.

Tôi đã thử sử dụng Extended Euclidean algorithm, nhưng phải làm gì khi b và m không đồng nhất? Cụ thể là mentioned mà b và m cần phải là đồng nhất.

tôi đã cố gắng sử dụng mã here, và nhận ra rằng ví dụ: 3 * x mod 12 không phải là ở tất cả có thể cho bất kỳ giá trị của x, nó không tồn tại!

Tôi nên làm gì? Thuật toán có thể được sửa đổi bằng cách nào đó không?

Answer 1

Đúng, bạn gặp sự cố. x không có giải pháp trong b*x = 1 mod m nếu b và m có ước số chung. Tương tự, trong vấn đề ban đầu của bạn a/b = y mod m, bạn đang tìm kiếm y như vậy mà a=by mod m. Nếu có thể chia hết cho số gcd(b,m), thì bạn có thể chia cho yếu tố đó và giải quyết cho y. Nếu không, thì không có y nào có thể giải phương trình (tức là a/b mod m không được xác định).

Answer 2

Kiểm tra điều này: http://www.math.harvard.edu/~sarah/magic/topics/division Điều đó có thể hữu ích. Nó giải thích các phương pháp phân chia mô-đun.

Answer 3

Lý do b và m phải là nguyên tố trùng nhau là do Định lý còn lại của Trung Quốc. Về cơ bản các vấn đề:

3 * x mod 12

Có thể được coi là một vấn đề hợp chất liên quan đến

3*x mod 3 và 3*x mod 4 = 2^2

Bây giờ nếu b không nguyên tố cùng nhau đến 12, điều này cũng giống như cố gắng để chia cho zero . Do đó câu trả lời không tồn tại!

Điều này là do lý thuyết trường trong đại số trừu tượng. Một trường cơ bản là một tập hợp có phép cộng, trừ, nhân và phân chia rõ ràng. Một trường hữu hạn luôn luôn là dạng GF (p^n), trong đó p là số nguyên tố và n là một số nguyên dương, và các phép toán là phép cộng và phép nhân modulo p^n. Bây giờ, 12 không phải là một quyền lực chính, do đó, vòng của bạn không phải là một trường. Vì vậy, vấn đề này không thể được giải quyết cho bất kỳ b mà không phải là coprime để m.