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

  • $\begingroup$ 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$? $\endgroup$ – user44197 Jan 11 '14 at 17:39
  • $\begingroup$ @user44197 how to factor $n$ when knowing $e$ and $d$. $\endgroup$ – 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.$$

  • $\begingroup$ I was doing it similarly but didn't know how to get the $k$. But this explanation is clear, thanks! $\endgroup$ – John Smith Jan 11 '14 at 17:44
  • 1
    $\begingroup$ @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$. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – John Smith Jan 11 '14 at 17:37
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jan 11 '14 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.