Thuật toán euclid mở rộng

Tháng Tám 23, 2016Tháng Tám 23, 2016 huynhduyidolchinese remainder theorem, crt, diophante, inveres modulo, math, num theory

Tác giả: Huỳnh Văn Duy

Có thể nói vào lập trình đo lường thì các bài toán về số học tập chiếm 1 phần khá lớn. Vào đó, trong những thuật toán được biết đến nhiều duy nhất là lời giải euclid mở rộng, thuật toán này rất có thể giải quyết rất nhiều bài toán liên quan đến số học. Nên bây giờ chúng ta sẽ tìm hiểu về nó.

Bạn đang xem: Thuật toán euclid mở rộng

ĐẦU TIÊN TA CẦN TÌM HIỂU MỘT CHÚT VỀ THUẬT TOÁN EUCLID NGUYÊN THỦY

Lịch sử thuật toán Euclid:

Thuật toán Euclid là giữa những thuật toán cổ nhất theo luồng thông tin có sẵn đến, từ lúc nó xuất hiện trong cuốn Euclid’s Elements khoảng năm 300 trước công nguyên. Euclid mở đầu đã trình bày rõ ràng vấn đề về mặt hình học, như vấn đề tìm ra một thước đo bình thường cho độ dài hai đường thẳng, và thuật toán của ông đang xử lý bằng cách lặp lại phép trừ đoạn dài thêm hơn nữa cho đoạn ngắn hơn. Mặc dù nhiên, thuật toán đã phần đông không được phát hiện ra vày Euclid cùng nó đã có thể được biết đến sớm rộng 200 năm. Nó cũng đã được nghe biết bởi Eudoxus of Cnidus (khoảng năm 375 trước công nguyên) và Aristotle (khoảng năm 330 trước công nguyên).

Mô tả thuật toán:

Cho 2 số thoải mái và tự nhiên a và b, ko đồng thời bằng 0: khám nghiệm nếu b bởi 0, thì a là cầu chung lớn số 1 (UCLN). Trường hợp không, tái diễn xử lý thực hiện b và phần còn lại sau khi lấy a phân tách cho b. Phần còn lại sau khi chia a cho b thường được viết là a thủ thuật b.

Các thuật toán này rất có thể sử dụng vào bất kì hoàn cảnh nào khi còn phần dư. Điều này bao hàm các nhóm đa thức như nhóm số nguyên Gauxơ. Thuật toán không những áp dụng cho số tự nhiên và thoải mái mà còn vận dụng cho nhiều trường hợp tổng thể khác sẽ tiến hành mô tả chi tiết sau.

Xem thêm: Smallpox Is A Dangerous Disease Malaria Is A Dangerous Disea Se

Thuật toán rất có thể được thiết đặt rất đối chọi giản:

#include #include using namespace std;#define builtin_gcd __gcdint gcd(int a, int b) if(b==0) return a; else return gcd(b,a%b);int main(){ cout

Dĩ nhiên, ngôn từ lập trình C++ cũng cung cấp cho họ một hàm gồm sẵn nhằm tìm mong chung lớn số 1 của nhị số bằng thuật toán euclid, sẽ là hàm __gcd(a, b) vẫn trả về cầu chung lớn số 1 của hai số a và b.

THUẬT TOÁN EUCLID MỞ RỘNG

Phương trình diophantine:

(1)

Theo định lí Bézout (Bézout’s indentify): cho hai số nguyên a, b khi đó luôn tồn tại nhị số x, giống hệt cho:

Người ta cũng minh chứng được phương trình trên bao gồm nghiệm khi và chỉ còn khi gcd(a, b) = c. Cùng như thế có nghĩa là phương trình diophante rất có thể có vô số nghiệm, cùng từ từng một nghiệm ta có thể sinh ra đều nghiệm khác.

Định nghĩa số nguyên k sao cho:

. Phân chia vế theo vế phương trình đến ta được phương trình mới

Dễ thấy

và đó là một nghiệm của phương trình (1). Mang sử là một trong nghiệm không giống của phương trình (1), ta có:

Suy ra:

(3), nghĩa là a là cầu của , và là ước của . Yêu cầu ta có: cùng với r là một số nguyên. Cụ vào (3), ta được:

Trong đó:

hay

Như vây, nếu

có một nghiệm bất kỳ thì toàn bộ các nghiệm sẽ sở hữu được dạng:

Ví dụ: Tìm tất cả các nghiệm của phương trình

.

Xem thêm: Nhắm Mắt Ơ Thờ Anh Không Muốn Lạc Vào Trong Nỗi Đau Này, Lời Bài Hát Chúng Ta Không Thuộc Về Nhau

Đầu tiên, ta xét , do bắt buộc phương trình chắc chắn rằng có nghiệm.Áp dụng thuật toán Euclid, ta có:Bây giờ, ta tìm kiếm cách biểu diễn 3 bởi một mối quan hệ tuyến tính thân 258 cùng 147. Phụ thuộc vào trên, ta có:Tiếp theo, ta viết , cùng nhân phương trình mang đến 123 vị . Ta được:.Vậy một nghiệm của phương trình là: , và các nghiệm khác gồm dạng:

Cài đặt ráng thể:

// Extended euclid solve diophantine linear equation#include #define x first#define y secondusing namespace std;typedef long long ll;typedef pair ii;ll a, b, c;ii extended_gcd(ll a, ll b) if (b == 0) return ii(1, 0); ii qr = ii(a / b, a % b); ii st = extended_gcd(b, qr.y); return ii(st.y, st.x - qr.x*st.y);void extended_gcd2(ll a, ll b, ll &X, ll &Y) // another version ll d = __gcd(a, b); ll m = a, n = b; ll xm = 1; // (ym = 0) m = a = a*1 + b*0 ll xn = 0; // (yn = 1) n = a = a*0 + b*1 while (n) ll q = m / n; ll r = m - q*n; ll xr = xm - q*xn; m = n, xm = xn; n = r, xn = xr; X = xm * (c/d); Y = ((d - a*xm) / b) * (c/d);int main() freopen("in.txt", "r", stdin); scanf("%lld %lld %lld", &a, &b, &c); ll d = __gcd(a, b); ii ex = extended_gcd(a, b); printf("%lld %lldn", c/d*ex.x, c/d*ex.y); ll X, Y; extended_gcd2(a, b, X, Y); printf("%lld %lldn", X, Y); assert(c/d*ex.x == X && c/d*ex.y == Y); return 0;NGHỊCH ĐẢO MODULO

Một một trong những ứng dụng đặc trưng nhất của thuật toán Euclid không ngừng mở rộng đó chính là dùng nhằm tìm nghịch hòn đảo modulo:

Nhận xét: nếu , giải phương trình

Ta có:

Khi đó

được gọi là nghịch đảo của a theo modulo m (ký hiệu )

Ví dụ: a = 7, m = 10, Xét phương trình

Nghiệm

Khi đó:

TỔNG KẾT:

Thuật toán Euclid mở rộng có thể dùng để giải phương trình Diophantine Họ nghiệm của phương trình Diophantine khi đã có nghiệm x, y là:

BONUS: ĐỊNH LÍ THẶNG DƯ nước trung hoa (CHINESE REMAINDER THEOREM)

Định lý thặng dư trung quốc là tên tín đồ phương tây đặt cho định lý này. Người nước trung hoa gọi nó là câu hỏi Hàn Tín điểm binh. Hàn Tín là một trong những danh tướng tá thời Hán Sở, từng được phong tước vương thời Hán Cao Tổ lưu giữ Bang đang dựng nghiệp. Sử ký bốn Mã Thiên viết rằng Hàn Tín là tướng tá trói con kê không nổi, tuy thế rất có tài quân sự. Tục truyền rằng lúc Hàn Tín điểm quân số, ông mang lại quân quân nhân xếp hàng 3, mặt hàng 5, sản phẩm 7 rồi báo cáo số dư. Từ đó ông tính đúng mực quân số đến từng người.

Gần đây, định lý số dư Trung Quốc có khá nhiều ứng dụng trong các bài toán về số nguyên lớn áp dụng vào kim chỉ nan mật mã. – Wikipedia

Bản chất của vấn đề Hàn Tín điểm binh là giải phương trình đồng dư bật nhất được mô tả tổng quát như sau: