Small Prime Difference in RSA

Question

In RSA, the $p$ and $q$ should be randomly generated, and they are the same size. The difference between $p$ and $q$ should not be small.

Suppose that $u=|p-q|<20$ and $p \times q =2189284635403183$. Find the values of $p$ and $q$.

I have no idea how to compute $p$ and $q$. I use calculator to compute square root of thr product. But it is definitely not correct as I get something ends with $2$. Can anyone help me?

Answer 1

We want a non-trivial factorization of a moderate odd integer $n$ into positive integers $p$ and $q$, knowing that such factorization with $|p-q|$ suitably small exists.

Perhaps the most elementary method answering the question is trial division by integers starting at $\lfloor\sqrt n\rfloor$, going down. This succeeds after checking divisibility of $n$ by at most (very slightly less than) $|p-q|\over2$ candidates. Some easy speedups are possible (skipping even candidates, generalizable to candidates divisible by the first few small primes).

The method described in this comment, and equivalently in this answer, also work. They succeed after testing at most $|p-q|\over2$ candidates. Depending on implementation (of the squareness test in particular), speed can be slower or faster than trial division.

---

I'll describe a method that avoids any trial and error under the assumption that $|p-q|<(64n)^{1/4}$. With the given $n=2189284635403183$, that translates to $|p-q|<19348$, which very comfortably holds since $|p−q|<20$ is given.

Theorem: Given any odd integer $n$, if there exist unknown integers $p$ and $q$ with $n=p\times q$ and $(p-q)^2<8\sqrt n$, the following non-iterative algorithm outputs these $p$ and $q$:

1. compute $a=\lceil\sqrt n\rceil$ (that is, the smallest non-negative integer which square is at least $n$)
2. compute $s=a^2-n$, which amazingly will be the square of some integer
3. compute $b=\sqrt s$ (that is, the non-negative number which square is $s$)
4. output $a+b$ and $a-b$.

Proof:

• Without loss of generality we reorder $p$ and $q$ so that $p\ge q$. We know $p$ and $q$ are odd, since their product is. Thus, when we define $c={p+q\over2}$ and $d={p-q\over2}$, these are non-negative integers. Further, $c^2-n=d^2$ holds.
• In step 1 of our algorithm, $a$ is computed as the only non-negative integer $x$ satisfying $x^2-n\ge 0$ and $(x-1)^2-n<0$. From $c^2-n=d^2$ it follows that $x=c$ satisfies the first of these conditions. The second condition is $(x-1)^2<n$, which is satisfied if $0\le x-1<\sqrt n$, that is $1\le x<\sqrt n+1$. $x=c$ satisfies $1\le x$, since $c={p+q\over2}$ with $p\ge1$ and $q\ge1$. Thus $c<\sqrt n+1$ would imply $a=c$.
• Since $c\ge0$, we can equivalently prove $c^2<(\sqrt n+1)^2$, that is $n+d^2<(\sqrt n+1)^2$, that is $({p-q\over2})^2<(\sqrt n+1)^2-n$, that is $(p-q)^2<4((\sqrt n+1)^2-(\sqrt n)^2))$, that is $(p-q)^2<4(2\sqrt n+1)$. It follows from our hypothesis $(p-q)^2<8\sqrt n$.
• We have shown that step 1 produces $a=c$; thus step 2 produces $s=a^2-n$ equal to $d^2$; thus step 3 produces $b$ equal to $d$; thus step 4 outputs $p$ (for $a+b$) and $q$ (for $a-b$), Q.E.D.

---

The above is the basic Fermat factorization method, but reduced to its first step and without any test (because we can do without it in the question, and that simplifies our algorithm and proof). The full basic Fermat method performs $\Big\lceil{(p-q)^2\over8\sqrt n}\Big\rceil$ tests, and thus requires less computing effort than trial division from $\sqrt n$ by a factor of $O\big({\sqrt n\over|p-q|}\big)$ as a first-order approximation; this can be huge, but only when $|p-q|$ is much smaller than likely under random selection of $p$ and $q$ in an interval of width a sizable fraction of $\sqrt n$. Description of Fermat's methods, classic improvements, and computing cost, would be the subject of a different question.

Answer 2

First, note that if you know $p-q=a$ and $p+q=b$, for some $a,b$, you have two equations with two unknowns and can solve for $p,q$.

Now,

$$ n=p*q=\left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2$$

Rearrange

$$ \left(\frac{p+q}{2}\right)^2 = n + \left(\frac{p-q}{2}\right)^2$$

Then start guessing values for $p-q$. Start with $2$ and substitute in to the equation. Then check to see if the square root of the right hand side is a whole number. If it is, you have found $p-q$. You can then solve for $p+q$ easily. Then you can solve for $p,q$. Otherwise, try 4, 6, 8,... until RHS is a square.