I am having a trouble finding a way to factorize the RSA number besides using brute force.
The public key is $(n,e) = (22663, 59)$ and the private is $(n,d) = (22663, 379)$.
Using brute force starting from $\sqrt{22663}$ and going down by odd numbers I found that
$n = 131 * 173$
Is there a better way to do this? This was on the test and it stated "Find the factorization with the help of public and private key."
Best Answer
If you know both $e$ and $d$ then from $ed\equiv 1\pmod {(p-1)(q-1)}$ we find that there exists $k$ such that $$ed = 1+k(p-1)(q-1) = 1+k(N-p-q+1). $$ Since $p,q\ll N$, let $k$ be the nearest integer to $\frac {ed}N$ and guess that $N-\frac{ed-1}k-1=p+q$. Knowing $p+q$ and $pq=N$, you find $p,q$ as roots of $X^2-(p+q)X+pq=0$.
Here: $ed = 22361$, so apparently $k=1$. Thus $p+q=N-ed+2=304$ and $$ p,q =152\pm\sqrt{152^2-22663}=152\pm 21.$$