RSA - finding $p$ and $q$

Question

If the public key $(e,n)$ and the private key $(d,n)$ are known, how can I find the $p$ and $q$ primes by the easiest way? When $n$ and $\varphi(n)$ are given was easy to solve, but this issue I can't manage.

Answer 1

Here is an easy way to do that, instead of choosing random g always take this as prime took a prime table []={2,3,5,7,11,13,17,19,23..}

below is pseudo code
choose g from prime table.
let g = 2;
k = ed-1;
  while(k%2==0):
     k= k/2;
     x = g^k mod n
     if(x > 1):
       y = gcd(x-1,n)
       if(y > 1)
       p=y
       q = n/y
       exit
else go step 1 choose nest prime as g
 repeat until you get p and q

Answer 2

Suppose $n=pq$ for large primes $p,q$ and $ed \equiv 1 \mod (p-1)(q-1)$, the usual RSA setup. Let $k=de-1$. Now pick any number $g$, so that $g^{k/2}$ is a square root of one modulo $n$. In $Z/n \cong Z/p \oplus Z/q$, square roots of 1 look like $(x,y)$ where $x=\pm 1$ and $y=\pm 1$. So if you are lucky, $g^{k/2}-1$ has image $(0,-2)$ or $(-2,0)$ in $Z/p \oplus Z/q$. In this case $\operatorname{gcd}(g^{k/2}-1,n)=p$ or $q$. If you are unlucky, try again with a different $g$.