$p$ and $q$ 512-bit primes. What size in bits is $N=pq$?

Question

$p$ and $q$ 512-bit primes. What size in bits is $N=pq$?

I have that $p$ and $q$ are between $2^{512}-1$ and $2^{511}$, but cannot work out the rest.

Thanks in advance.

Answer 1

(To clear it up for anyone who might not know why $p$ and $q$ are bounded by their 'bit size':)

If $p$ and $q$ are $512$-bit primes, first we would need to see what the largest value of $p$ and $q$ could possibly be.

So consider some simple cases: If $p$ and $q$ are $3$-bit primes, then the maximum possible binary number they could be is $\left(111\right)_2$. This number is $7 = 2^3 - 1$.

After trying a few values of 'bit sizes' out. You will soon find that a number that has $n$ bits has maximum value $2^n-1$.

Let $p$ and $q$ be as $\textit{large}$ as possible for an upper bound on $N$: $\left\vert{N}\right\vert \leq \left\vert{p}\right\vert \cdot \left\vert{q}\right\vert \leq \left(2^{512}-1\right)\left(2^{512}-1\right) = 2^{1024}-2\cdot 2^{512} + 1 = 2^{1024}- 2^{513} + 1 $

Let $p$ and $q$ be as $\textit{small}$ as possible for a lower bound on $N$: $\left\vert{N}\right\vert \geq \left\vert{p}\right\vert \cdot \left\vert{q}\right\vert \geq \left(2^{511}\right)^2 = 2^{1022}$