Tight Bounds on the Sum and Difference of Divisors of RSA Challenge Numbers

Question

The title says it all: given that $n$ of a given length $d$ is a RSA Challenge Number where $n=pq$, where $p$ and $q$ are two primes of length $d/2$. My question is, knowing how the RSA numbers are generated, what are some tight upper and lower bounds of the sum and difference of $p$ and $q$? I'm asking this question as I am working on a factoring algorithm and it works best with tight bounds.

EDIT: For an example, I am specifically interested in RSA-2048.

Answer 1

n mod 6 would tell you if you're dealing with p congruent to q mod 6. That would limit you to the largest pair of primes that are both congruent or not.

You can likely do better. For example via digit elimination mod 3, you can show RSA 2048 is 27 mod 30 if I did the calculation correctly. it really shouldn't be because that would make it divisible by 3, but it appears to be.

Answer 2

Well, it is known that if the primes $p,q$ have approximately the same length, then there is a simple attack called Fermat factoring.

To this end, note that one can write $u=(p+q)/2$, $v=(p-q)/2$, $p=u+v$, and $q=u-v$ if $p>q$.

If $p,q$ are close together, then $v=(p-q)/2$ is small and $u$ is only slightly larger than $\sqrt n$.

Then use the algorithm to start from $u=\lfloor\sqrt n\rfloor +1$ and add to $u$ until you find that $u^2-n$ is a perfect square. Then $v=\sqrt{u^2-n}$ and $p,q$ are given as above. Done.