3
$\begingroup$

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?

$\endgroup$
2
  • $\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, 2018 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$ Nov 8, 2018 at 14:33

1 Answer 1

4
$\begingroup$

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

$\endgroup$
4
  • $\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$ Nov 8, 2018 at 14:31
  • 1
    $\begingroup$ With $N$ at hand, trial division allows a small improvement :-) $\endgroup$
    – fgrieu
    Nov 8, 2018 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, 2018 at 15:41
  • $\begingroup$ Illmari, could you write the reason for the bound into the question? $\endgroup$
    – kelalaka
    Nov 8, 2018 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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