solution

Một chương trình sinh khóa RSA cần kiểm tra đầy đủ điều kiện trước khi phát hành khóa, thay vì tin tưởng mù quáng đầu vào. Cho ba số nguyên dương $p, q, e$ (không đảm bảo $p, q$ là số nguyên tố), hãy thực hiện tuần tự:

1. Kiểm tra $p$ và $q$ có đều là số nguyên tố hay không, và $p \ne q$. Nếu vi phạm, in INVALID.
2. Với $n = pq$, $\varphi(n) = (p-1)(q-1)$, kiểm tra $1 < e < \varphi(n)$ và $\gcd(e, \varphi(n)) = 1$. Nếu vi phạm, in INVALID.
3. Nếu mọi điều kiện thỏa, tính số mũ bí mật $d$ (nghịch đảo của $e$ modulo $\varphi(n)$) và in ra VALID n phi(n) d.

Ví dụ: $p=61, q=53, e=17$ đều thỏa mãn $\Rightarrow$ in VALID 3233 3120 2753. Với $p=4$ (không phải số nguyên tố) $\Rightarrow$ in INVALID.