$\Huge\text{The problem: given d and e, can we factorize N ?}$

-------

Ta có: $de \equiv 1 (mod$ $\phi(N))$.
Gọi $k = de - 1 = t * \phi(N)$, $k$ chẵn.
$\rightarrow k = 2^i * r$, với $r$ lẻ, $i \ge 1$.

Để phân tích $p, q$ thì ta sẽ làm như sau:
Dựa trên bài toán tìm nghiệm $x$ thỏa mãn $x^2 \equiv 1 \pmod N$.

Chọn $1$ số ngẫu nhiên $g$ sao cho $gcd(g, N) = 1$ và $1 < g < N$.
$\rightarrow$ $g^{\phi(N)} \equiv 1 \pmod N$ theo định lí Euler.
$\rightarrow$ $g^k \equiv 1 \pmod N$ vì $k$ là bội của $\phi(N)$.

Thuật toán của ta sẽ là:
- Ban đầu ta gọi $x$ $=$ $g^{\frac{k}{2}}$, ta có phương trình $x^2 \equiv 1 \pmod N$. $(*)$
- Dùng CRT để giải phương trình này ta có 4 nghiệm: $x = 1, x = -1,x = a,x = -a$.

- Với $x = a$ $(mod$ $pq)$ và $1 < a < pq$ và $a$ thỏa mãn:
$$
\begin{cases}
a \equiv 1 \mod p \\
a \equiv -1 \mod q
\end{cases}
$$
Thì ta có thể lấy $gcd(a - 1, pq)$ là sẽ ra được $p$.

Vì ta đã biết giá trị $a = g^{\frac{k}{2}}$ nên ta sẽ thay vào rồi lấy GCD luôn.

- Ta thấy phương trình luôn có nghiệm $x = 1$, khi đó ta sẽ lặp lại bước $(*)$ với $x$ giảm dần $x =g^{\frac{k}{2}}, g^{\frac{k}{4}}, g^{\frac{k}{8}}, ..., g^{\frac{k}{2^i}}$ để tiếp tục tìm được nghiệm $a$ thỏa mãn. Nếu vẫn không tìm được thì ta sẽ random số $g$ mới.

-----

Resource:
- [RSA: how to factorize N given d](https://www.di-mgt.com.au/rsa_factorize_n.html)
- [Twenty Years of Attacks on the RSA Cryptosystem](https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf)