# RSA Prime factorization for known public and private key

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."

• Not sure what you mean by the word this. Do you want to know how to calculate $e$ knowing $d$ and the factorization of $n$ or how to factor $n$? – user44197 Jan 11 '14 at 17:39
• @user44197 how to factor $n$ when knowing $e$ and $d$. – John Smith Jan 11 '14 at 17:41

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.$$
• I was doing it similarly but didn't know how to get the $k$. But this explanation is clear, thanks! – John Smith Jan 11 '14 at 17:44
• @JohnSmith Note that $k$ may be much larger, often beyond brute force, if $e$ is large (not likely, but is worth considering) but fortunately there is an efficient randomized algorithm that can factor $n$ given $e$ and $d$ in polynomial time (no matter what $k$ is). It is clear the numbers were chosen to be easy for your test, just noting for further interest that there are better approaches that do not rely on guesswork to find $k$. – Thomas May 15 '14 at 10:51
You have $$ed=22361=(p-1)(q-1)+1\\ pq=22663\\ (p-1)(q-1)=22360\\ p+q=304\\p(304-p)=22663$$and you have a quadratic.
• That's similar to what I was trying.. but there's seems to be some guessing here, right? I had the equation as $ed = k*(p-1)(q-1) + 1$ and didn't know how to get k. – John Smith Jan 11 '14 at 17:37
• Since $ed \lt pq$, we must have $k=1$ because $(p-1)(q-1)$ isn't much smaller than $pq$. While you could use a higher $k$, nobody would. – Ross Millikan Jan 11 '14 at 17:42