RSA finding p and q integer with condition

Question

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

Answer 1

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.