> **Lưu ý:** Đây là bộ testcase tạo ra sau khi kỳ thi kết thúc. Không đại diện cho testcase và điểm số thực tế. ## Đề bài Thuật toán RSA hoạt động như sau: chọn hai số nguyên tố lẻ phân biệt $p, q$ rồi tính $n = pq$. Tính hàm Euler $$ \phi(n) = (p-1)(q-1) $$ và chọn một số nguyên $e$ sao cho $1 < e < \phi(n)$ và $\gcd(e, \phi(n)) = 1$. Cuối cùng, tính số nguyên $d$ là nghịch đảo của $e$ theo modulo $\phi(n)$, tức là $ed \equiv 1 \pmod{\phi(n)}$. - Khóa công khai: $(n, e)$. - Khóa bí mật: $(n, d)$. - Mã hóa: $c = m^e \bmod n$. - Giải mã: $m = c^d \bmod n$. Cho khóa công khai $(n, e)$ và thông điệp đã mã hóa $c$, hãy tìm lại thông điệp gốc $m$. ## Đầu vào - Dòng đầu tiên chứa một số nguyên dương $T$ — số bộ dữ liệu cần giải mã. - $T$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $n, e, c$ mô tả một khóa công khai và thông điệp đã mã hóa tương ứng. ## Đầu ra Với mỗi bộ dữ liệu, in ra trên một dòng thông điệp gốc $m$. ## Ràng buộc | Đại lượng | Ràng buộc | | --- | --- | | Số bộ dữ liệu | $1 \le T \le 100$ | | Modulus | $2 \le n \le 10^{12}$, $n = pq$ với $p, q$ là hai số nguyên tố lẻ phân biệt | | Khóa công khai | $1 < e < n$ | | Thông điệp mã hóa | $0 < c < n$ | | Giới hạn thời gian | $1$ giây | | Giới hạn bộ nhớ | $256$ MB | Đề bài gốc chỉ nêu $1 < e < n$, nhưng để phép giải mã RSA có nghiệm duy nhất thì bắt buộc phải có $\gcd(e, \phi(n)) = 1$ — chỉ khi đó nghịch đảo modular $d$ mới tồn tại. Bộ test của bài này luôn đảm bảo điều kiện $\gcd(e, \phi(n)) = 1$, cũng như đảm bảo $n$ luôn là tích của đúng hai số nguyên tố lẻ phân biệt. Vì $p, q$ đều lẻ và khác nhau nên giá trị nhỏ nhất có thể có của $n$ trên thực tế là $3 \times 5 = 15$, dù ràng buộc hình thức chỉ ghi $n \ge 2$. Lưu ý ràng buộc là $1 < e < n$ chứ không phải $1 < e < \phi(n)$. Vì $\phi(n) < n$ nên bộ test **có** những trường hợp $e > \phi(n)$; khi đó vẫn giải mã bình thường bằng $d = (e \bmod \phi(n))^{-1} \bmod \phi(n)$, vì $c^{e} \equiv c^{e \bmod \phi(n)}$ trên các lớp thặng dư liên quan. Bộ test cũng có những trường hợp $\gcd(m, n) > 1$ (thông điệp gốc chia hết cho $p$ hoặc $q$): phép giải mã RSA vẫn cho kết quả đúng, nhưng lời giải nào giả định $\gcd(c, n) = 1$ để dùng định lý Fermat nhỏ sẽ sai. ## Ví dụ ::sample{index=0} ## Giải thích ví dụ Với $n = 91 = 7 \times 13$, ta có $\phi(91) = 6 \times 12 = 72$. Với $e = 43$, nghịch đảo modular là $d = 67$ vì $43 \times 67 = 2881 = 40 \times 72 + 1 \equiv 1 \pmod{72}$. Giải mã thông điệp $c = 19$: $m = 19^{67} \bmod 91 = 33$, đúng bằng đáp án mẫu. ## Kiến thức liên quan > Hãy tự giải bài trước đã. Chỉ mở phần gợi ý bên dưới khi bạn đã thật sự bí. :::spoiler - [Lũy thừa nhị phân](https://wiki.vnoi.info/algo/algebra/binary_exponentation.md) — *Tiếng Việt* — Luỹ thừa nhanh theo modulo - [Nghịch đảo modulo](https://wiki.vnoi.info/algo/math/modular-inverse.md) — *Tiếng Việt* — Cách tính nghịch đảo modular - [Phi hàm Euler](https://wiki.vnoi.info/algo/algebra/phi-ham-euler) — *Tiếng Việt* — Hàm Euler phi và ứng dụng trong số học modulo - [Modulo cơ bản — VNOI Wiki](https://wiki.vnoi.info/algo/math/modulo) — *Tiếng Việt* — Đồng dư, định lý Euler và Fermat nhỏ, Euclid mở rộng khi modulo không nguyên tố. :::