Định Lý Thặng Dư Trung Hoa

     

Định lýsố dưTrung Hoa (Định lý thặng dư Trung Hoa), haybài toán Hàn Tín điểm binh, là 1 trong những định lý nói đến nghiệm củahệ phương trìnhđồng dưbậc nhất. Dẫu vậy trong ngành mật mã , bọn họ sẽ dùng định lý này để áp dụng vào câu hỏi tăng vận tốc giải mã mang đến thuật toán RSA.

Bạn có thể xem chi tiết thuật toán phần dư trung quốc ở link: https://vi.wikipedia.org/wiki/Định_lý_số_dư_Trung_Quốc

Trong các trường đúng theo ta ý muốn tìm phương pháp để tăng tốc độ đo lường và thống kê Modulo các phép toán, các số lớn sẽ được phân bóc thành số nhỏ hơn là các cặp nguyên tố cùng nhau, tiếp nối dùng thuật toán phần dư Trung Hoa.

Bạn đang xem: định lý thặng dư trung hoa


Nội dung


Các cách thuật toán

Để tính $displaystyle A pmodM$ cùng với M khá phệ và A là biểu thức số học tập nào đó.

Xem thêm: 5 Thực Phẩm Không Nên Ăn Với Tôm Và Thịt Gà Có Kỵ Nhau Không Nên Ăn Cùng Thịt Gà

Bước 1: so với $displaystyle M=m_1*m_2*…*m_k$ cùng với $displaystyle m_i, m_j, i eq j$ là những số nguyên tố thuộc nhau.

Xem thêm: Công Bố Kết Quả Tổng Điều Tra Dân Số Hà Nội Năm 2014, Khi Dân Số Hà Nội 2014

Bước 2: Tính $displaystyle M_1=M/m_1,M_2=M/m_2,…,M_k=M/m_k$Bước 3: xác minh $displaystyle a_i=Amodm_i, 1 leq i leq k$Bước 4: Tính $displaystyle c_i=M_i*(M_i^-1 modm_i), 1 leq i leq k$Bước 5: tiếp nối sử dụng công thức: $displaystyle (sum_i=1^k a_i c_i) pmodM$

Chú ý: Để tính được theo định lý phần dư trung hoa thì $displaystyle GCD(m_i, m_j) = 1, i eq j$, tức mi phải là những số nguyên tố thuộc nhau.

Ví dụ

Ví dụ 1: Áp dụng định lý phần dư Trung Hoa, tính $displaystyle 17^8 mod77$

Bước 1: $displaystyle M=77=m_1*m_2=7*11$ thoản mãn GCD(7,11)=1 Bước 2: Tính $displaystyle M_1=M/m_1=77/7=11$$displaystyle M_2=M/m_2=77/11=7$Bước 3: xác định $displaystyle a_1=Amodm_1=17^8mod7=2$ (Dùng bình phương cùng nhân)$displaystyle a_2=Amodm_2=17^8mod11=4$ (Dùng bình phương cùng nhân)Bước 4: Tính $displaystyle c_1=M_1*(M_1^-1 modm_1)=11*(11^-1 mod7)=11*2=22$ (Dùng Euclid nhằm tính nghịch hòn đảo vành Zn)$displaystyle c_2=M_2*(M_2^-1 modm_2)=7*(7^-1 mod11)=7*8=56$ (Dùng Euclid để tính nghịch hòn đảo vành Zn)Bước 5: kế tiếp sử dụng công thức: $displaystyle (sum_i=1^k a_i c_i) pmodM = a_1 c_1 + a_2 c_2 = 2*22 + 4*56=268=37 pmod77$

BÀI TẬP

Sử dụng định lý phần dư trung hoa tính quý giá biểu thức:

$displaystyle 25^30 pmod7*8$$displaystyle 70^254 pmod11*13$$displaystyle 60^-1 pmod11*13$$displaystyle ((21^100+33^-1)*45^51) pmod7*9*11$$displaystyle (19^125+25^51)*(47^21/37) pmod9*11*13$
TAGS