RSA semiprime distance between $P$ and $\sqrt{N}$.

223 Views Asked by At

Suppose $P < Q$ and $PQ=N$, where both $P$ and $Q$ are prime (including $2$). What's the distance $P$ from $\sqrt{N}$?

1

There are 1 best solutions below

0
On

Claim. If we have $PQ = N$ and $P \le Q \le 4P$ for some positive integers (or positive real numbers, or primes) $P$ and $Q$, then it must be the case that $\sqrt N - P \le P$: the furthest $P$ can ever be from $\sqrt N$ is $P$.

Proof. From $Q \le 4P$, multiply by $P$ on both sides to get $PQ \le 4P^2$, or $N \le 4P^2$. Both sides are positive, so we can take the square root to get $\sqrt N \le 2P$. Subtracting $P$ from both sides, we get $\sqrt N - P \le P$.

Notes:

  • Another way to state this conclusion is that $P \ge \frac12\sqrt N$.
  • Since $PQ = N$, this is equivalent to saying that $Q \le 2\sqrt N$, which can also be started as $Q - \sqrt N \le \sqrt N$.
  • A slightly stronger condition is that $Q - \sqrt N \le 2P$. We can also prove this algebraically. From $P \le Q \le 4P$, we have $(Q - P)(4P-Q) \ge 0$, or $5PQ - 4P^2 - Q^2 \ge 0$. We can rearrange this to $Q^2-4PQ + P^2 \le PQ$, which is equivalent to $(Q - 2P)^2 \le N$. Therefore $Q - 2P \le \sqrt N$, from which the conclusion that $Q -\sqrt N \le 2P$ follows.
  • In other words, both $P$ and $Q$ have to lie in the interval $[\sqrt N - P, \sqrt N + 2P]$.
  • In the case of prime numbers, we cannot of course have $Q = 4P$, and so we may assume $Q < 4P$; in this case, all the inequalities we conclude are also strict.