Tôi sẽ giải quyết vụ việc $e=2$; nếu $\gcd(e, \phi(n)) = 2$, thì điều này là đủ (vì chỉ cần tìm căn bậc hai của $c$ (bản mã), sau đó lấy $e/2$gốc rễ của điều đó.
Vì vậy, chúng tôi đã đưa ra $c$ và muốn tìm các giá trị $m$ s.t. $m^2 = c \pmod {p^2}$.
Chúng tôi bắt đầu bằng cách tìm các giá trị $m'$ s.t. $m'^2 = c \pmod p$; đây là một căn bậc hai mô-đun và có các thuật toán đã biết cho nó. Đơn giản nhất áp dụng nếu $p \equiv 3 \pmod 4$; trong trường hợp đó, $m' = \pm c^{(p+1)/4} \bmod p$. Các $p \equiv 1 \pmod 4$ trường hợp cũng có thể thực hiện được, nhưng là công việc nhiều hơn.
Với những giá trị đó, chúng tôi chuyển đổi chúng thành giá trị modulo $p^2$. Điều đó thậm chí còn dễ dàng hơn, bởi vì nếu chúng ta có $m = m' + xp$ (và $m$ sẽ luôn tương đương với một trong các $m'$ giá trị modulo $p$), sau đó chúng tôi có:
$$m^2 = (m' + xp)^2 = m'^2 + 2m'xp = c \pmod {p^2}$$
Và kể từ khi $c-m'^2$ là bội số của $p$, chúng ta có thể giảm điều này thành:
$2m'x = (c - m'^2)/p \pmod p$, hoặc $x = (2m')^{-1} (c - m'^2)/p \pmod p$
Và, $m = m' + px$ cung cấp cho bạn các giá trị của $m$ (và hãy nhớ rằng, có hai giá trị có thể có của $m'$ và do đó hai giá trị có thể có của $m$).
Cũng lưu ý rằng, vì chúng tôi đã quản lý để thực hiện mà không có bất kỳ thông tin cá nhân nào, điều này không hoạt động như 'mã hóa khóa công khai'
