0

Let's say we have $n=pq$ with $p,q$ prime. We can write $n=s^2-t^2$ for some whole numbers $s,t$.

Now prove that if $q<p\leq (1+\epsilon)\sqrt{n}$ then $s$ has at most $\frac{\epsilon^2}{2}\sqrt{n}$ values, i.e. the number of values we need to test to find $n=s^2-t^2$.

My attempt:

I figured, that $n=s^2-t^2 = (s+t)(s-t) = pq$, therefore $p=s+t$ and $q=s-t$ assuming $s,t\geq 0$

So $s+t \leq (1+\epsilon)\sqrt{n}$ and $ s-t \leq (1+\epsilon)\sqrt{n}$ which means $s \leq (1+\epsilon)\sqrt{n}$

But what then? Am I even on the right track?

Quotenbanane
  • 1,594
  • 2
    Does this answer your question? RSA: Factorising $n$ using square difference . Found using Approach0. – John Omielan May 21 '22 at 20:37
  • WLOG let $p>q$. It is easy to establish $\bmod 4$ that $q\ne 2$, so $p,q$ are odd. Hence $(s+t),(s-t)$ share no common factors. Therefore, there is only one pair $s,t$ such that $p=s+t$ and $q=s-t$. However, there is one more solution, to wit $s+t=pq$ and $s-t=1$. In this case there is also only one pair of $s,t$ that satisfy that relationship. So for $n=pq$ an odd semiprime, there are two and only two possible values for $s$ – Keith Backman May 21 '22 at 21:00

0 Answers0