Bài 7: Định lý phần dư Trung Hoa

Định lý số dư Trung Hoa (Định lý thặng dư Trung Hoa), hay bài toán Hàn Tín điểm binh, là một định lý nói về nghiệm của hệ phương trình đồng dư bậc nhất. Nhưng trong ngành mật mã , chúng ta sẽ dùng định lý này để áp dụng vào việc tăng tốc độ giải mã cho thuật toán RSA.

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

Trong nhiều trường hợp ta muốn tìm cách để tăng tốc độ tính toán Modulo các phép toán, các số lớn sẽ được phân tách thành số nhỏ hơn là các cặp nguyên tố cùng nhau, sau đó dùng thuật toán phần dư Trung Hoa.

Các bước thuật toán

Để tính ${\displaystyle A \pmod{M}}$ với M khá lớn và A là biểu thức số học nào đó.

• Bước 1: Phân tích ${\displaystyle M=m_{1}*m_{2}*…*m_{k}}$ với ${\displaystyle m_{i}, m_{j}, i \neq j}$ là các số nguyên tố cùng nhau.
• 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 định ${\displaystyle a_{i}=A\mod{m_{i}}, 1 \leq i \leq k}$
• Bước 4: Tính ${\displaystyle c_{i}=M_{i}*({M_{i}}^{-1} \mod{m_{i}}), 1 \leq i \leq k}$
• Bước 5: Sau đó sử dụng công thức: ${\displaystyle (\sum_{i=1}^k a_i c_i) \pmod{M}}$

Chú ý: Để tính được theo định lý phần dư Trung Hoa thì ${\displaystyle GCD(m_i, m_j) = 1, i \neq j}$, tức m_i phải là các số nguyên tố cùng nhau.

Ví dụ

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

• 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}=A\mod{m_{1}}=17^8\mod{7}=2}$ (Dùng bình phương và nhân)
  • ${\displaystyle a_{2}=A\mod{m_{2}}=17^8\mod{11}=4}$ (Dùng bình phương và nhân)
• Bước 4: Tính
  • ${\displaystyle c_{1}=M_{1}*({M_{1}}^{-1} \mod{m_{1}})=11*(11^{-1} \mod{7})=11*2=22}$ (Dùng Euclid để tính nghịch đảo vành Zn)
  • ${\displaystyle c_{2}=M_{2}*({M_{2}}^{-1} \mod{m_{2}})=7*(7^{-1} \mod{11})=7*8=56}$ (Dùng Euclid để tính nghịch đảo vành Zn)
• Bước 5: Sau đó sử dụng công thức: ${\displaystyle (\sum_{i=1}^k a_i c_i) \pmod{M} = a_1 c_1 + a_2 c_2 = 2*22 + 4*56=268=37 \pmod{77}}$

BÀI TẬP

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

1. ${\displaystyle 25^{30} \pmod{7*8}}$
2. ${\displaystyle 70^{254} \pmod{11*13}}$
3. ${\displaystyle 60^{-1} \pmod{11*13}}$
4. ${\displaystyle ((21^{100}+33^{-1})*45^{51}) \pmod{7*9*11}}$
5. ${\displaystyle (19^{125}+25^{51})*(47^{21}/37) \pmod{9*11*13}}$