Composite Prime Test to determine distance between P and Q

82 Views Asked by At

I have two composite primes (semiprimes) where $17*641 = 10897$ and $101*107 = 10807$.

Notice that $10897$ and $10807$ are almost equal. Their square roots are $104.38$ and $103.95$ respectively. But in the first case $17$ and $641$ are far apart (their difference is large) and in the second case $101$ and $107$ are near each other (their difference is small).

Is there a test one can perform on a composite prime to determine if its two factors are far apart or close together?

2

There are 2 best solutions below

0
On

Suppose $N=pq$ and we know the difference between $p$ and $q$, say $d=p-q$. Then $N=(q + d)q$ is a simple quadratic from which we could easily find $q$. That is to say, finding $d$ is as hard as factoring $N$, which I guess you already know is a hard problem for large $N$.

0
On

If $p-q = 2d$ and $p+q = 2m$ then $pq = (m+d)(m-d) = m^2 - d^2$ so $pq + d^2 = m^2$ is a square. So it's easy to check for a particular $d$ by checking whether $pq + d^2$ is a square. However, once $d$ gets large enough that it's not feasible to check individual candidates for $d$, things get hard.