Khi cùng một bản rõ m được gửi cho ba người với cùng e = 3 nhưng modulus khác nhau n1, n2, n3 (đôi một nguyên tố cùng nhau), kẻ tấn công thu được c_i = m^3 mod n_i. Dùng Định lý số dư Trung Hoa (CRT) ghép lại được x ≡ m^3 (mod n1·n2·n3). Vì m^3 < n1·n2·n3, ta có x = m^3 trong số nguyên, lấy căn bậc ba ra m.
Input:
100003 c1
100019 c2
100043 c3
Output:
42
Ba dòng, mỗi dòng gồm n_i c_i.
Ba modulus đôi một nguyên tố cùng nhau, e = 3, m^3 < n1·n2·n3.
Bản rõ m.
Ví dụ:
Đầu vào:
100003 74088
100019 74088
100043 74088
Đầu ra:
42
Giải thích:
Đang tải editor...