I'm given $N=p\,q$ and told that $44\,p\approx 17\,q$ (with the value given for $N$ some 49-digit integer 8124642558124642555899928124642555899924479992447).

In RSA $p$ and $q$ must be prime.

So how can I solve this equation?

I'm using Maple, I began with s := evalf(solve(eqns, [p, q])) with eqns := {N = p*q, 44*p = 17*q}.

The result is not a prime number. How can I put another condition to force $p$ and $q$ to be prime? Or am I missing something?

Note of the editor: superlative HUGE removed for $N$, since it is way too small for RSA being secure.

  • Well come to Cryptograhy. Is this a homework question or from a CTF? If so, please write it down with the source. What have you tried? The question will be better; Let $n =p q$, $p$ and $q$ are two disntinct primes, with the following relation $i q \approx j q$ where $i$ and $j$ are small primes. – kelalaka Nov 4 at 9:15
  • and the second condition is $i p \approx j q$? The question is not clear. – kelalaka Nov 4 at 9:17
  • Hi, sorry let me clarify the question. I have an exemple N= 812464255589992447, and 44*p ≈ 17q. how can i find p and q (RSA) ? p and q must be integer and primes at the same times. Thanks for your help – Jameslator Nov 5 at 18:53
  • ip≈jq like 44*p ≈ 17q – Jameslator Nov 6 at 9:24
  • 1
    Note: the problem statement does NOT says that $44\,p = 17\,q$. Arithmetic is an exact science! Hint: What would happen if you tried to factor $44\cdot17\,N$ by Fermat's factoring method? – fgrieu Nov 6 at 10:50

The question's attempt at resolution is headed in the wrong direction for two related reasons

  • It informs the math tool that 44*p = 17*q when the problem statement has $44\,p\approx 17\,q$. If we had $44\,p=17\,q$, then $p$ and $q$ could not be primes, as stated in the problem.
  • It is not informing the math tool that $p$ and $q$ are integers. I can't help about how to do that for Mapple, and it is off-topic anyway.

$N$ is way too small to be useful as an RSA modulus, and could be easily factored without the hint that $44\,p\approx 17\,q$. Anything below 100 decimal digits has long been factorable by a single PC in minutes (see this); the lowest considered reasonable by Y2K was 1024 bits ≈ 309 digits; current is double that, moving to triple or away from RSA in the long run.

This is an application of Fermat's factoring method. This method is very efficient to factor integers of the form $C=A\,B$ with $A\approx B$. The hint $44\,p\approx17\,q$ tells that $C=44\cdot17\,N$ must be of this form, with $\{A,B\}=\{44\,p,17\,q\}$. Once we have factored $44\cdot17\,N$ using Fermat's factoring method, we can easily get at $p$ and $q$.

Don't fall into the trap of thinking that we must specifically guard against Fermat's factoring method and extensions when choosing an RSA key. The likelihood that the product of random primes $p$ and $q$ of practical size can be factored in this way is infinitesimal.

Update: there must be some typo in the value given for $N$, since (as commented by kelalaka) the integer given has 4 prime factors.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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