I was wondering whether given a concrete $N = p \cdot q$ whether we can find a upper bound on $\Delta = | p - q|$ as function of $N$ e.g, $N^\delta$, and thus test whether a given $N$ is vulnerable to Fermat-Factoring?

  • $\begingroup$ Marc, are trying to say; in case of security, what are the bound of the difference $ a < |p-q| < b$ $\endgroup$ – kelalaka Nov 8 '18 at 13:41
  • $\begingroup$ @kelalaka, Yes I am wondering if it is possible to detect unsafe primes for RSA. "IF" it ever happens and in a way that It can be factored using Fermat's method. $\endgroup$ – Marc Ilunga Nov 8 '18 at 14:33

Given that $p$ and $q$ are prime, they must be at least $2$, so $|p-q| \le \frac 12N - 2$. I'm pretty sure that's the only hard upper bound one can give.

Of course, typically $p$ and $q$ are chosen at random from among primes having the same bitlength in binary, meaning that the expected value of $|p-q|$ is roughly proportional to $N^{\frac12}$.

  • $\begingroup$ Thanks for your answer, the hidden intent behind the question was also with regard to Fermat factoring methods and variants. Although It seems the way we generate primes for RSA is safe, I was wondering if there is a way to detect if a number is "Fermat"-factorable. In which case $|p - q| < N^{1/4}$ should be enough. P.S: This has probably low probability of happening but I am curious. ;) $\endgroup$ – Marc Ilunga Nov 8 '18 at 14:31
  • 1
    $\begingroup$ With $N$ at hand, trial division allows a small improvement :-) $\endgroup$ – fgrieu Nov 8 '18 at 15:20
  • 2
    $\begingroup$ Even if we could find "a way to detect if a number is Fermat-factorable", we'd need to insure that $6\,N$ can't be factored into $(2\,p)(3\,q)$ by Fermat's method. And same for $a\,b\,N$ with a wide choice of $a$ and $b$ coprime... $\endgroup$ – fgrieu Nov 8 '18 at 15:41
  • $\begingroup$ Illmari, could you write the reason for the bound into the question? $\endgroup$ – kelalaka Nov 8 '18 at 17:31

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.