Maximum length in bits of the product n=pq

Question

If p and q are two 1024-bit prime numbers, would the maximum length in bits of product $n=pq$ be ${1024}^2$ or $2^{1024}$?

I think it is ${1048576}={1024}^2$?

Also, would the least significant bit of $n$ be a $0$ or a $1$? I am assuming it would be $0$? Any explanation of what determines significance would be great

Answer 1

If $p$ and $q$ are 1024-bit primes, then by definition of the bit size of an integer (at least, a prime in a cryptographic context with glimpses of RSA), $2^{1023}\le p<2^{1024}$ and $2^{1023}\le q<2^{1024}$. Thus their product $n=pq$ verifies $2^{2046}\le n<2^{2048}$, and $n$ is a 2047-bit or 2048-bit integer. We show by exhibition that both cases are possible, with $p=q=2^{1023}+1155$ for the first case, and $p=q=2^{1024}-105$ for the second.

Hence the maximum length in bits of the product $n=pq$ is $2048=2\cdot1024$.

This generalizes to: for odd primes $p$ and $q$, the maximum length in bits of the product $n=pq$ is the sum of the bit length of primes $p$ and $q$; proof that this bound is tight can be obtained from the observation that $\forall k>1,\exists p\text{ prime with }2^{k-1/2}<p<2^k$, which itself follows from stronger versions of Bertrand's postulate.

Since $p$ and $q$ are large primes, they are odd, hence $pq$ is odd, hence the least significant bit of $n=pq$ is 1.

Addition: in common RSA key generation standards FIPS 186-4 appendix B.3 and ancestor ANSI X9.31-1998, it is chosen primes $p$ and $q$ with $2^{k-1/2}<p<2^k$ and $2^{k-1/2}<q<2^k$, which insures that $pq$ is exactly $2k$ bits.

Answer 2

Any integer $n$ can be represented in binary form in $\left \lfloor{log_2{n}}\right \rfloor + 1$ bits.

Now coming to your problem where $n = pq$. Number of bits to represent $n$ is $\left \lfloor{log_2{n}}\right \rfloor + 1 = \left \lfloor{log_2{pq}}\right \rfloor + 1 = \left \lfloor{log_2{p}+log_2{q}}\right \rfloor + 1$.

By the properties of the floor function, $\left \lfloor {x} \right \rfloor + \left \lfloor {y} \right \rfloor \le \left \lfloor {x+y} \right \rfloor \le \left \lfloor {x} \right \rfloor + \left \lfloor {y} \right \rfloor + 1$, and $\left \lfloor {log_2p} \right \rfloor = 1023$ and $\left \lfloor {log_2q} \right \rfloor = 1023$, we have

$1023+1023+1 \le \text{bits for representing n} \le 1023+1023+1+1$. Thus, simplifying to $2047 \le \text{bits for representing n}\le 2048$.

Added: Since primes are odd, and multiplication of odds is odd, $LSB(n) = 1$. (assuming neither of them is 2).

Answer 3

No, the total number of bits after multiplication will be 2*1024. In binary form take for eg. 3 (2 bits = 11) * 3 (2 bits = 11) = 9 (4 bits = 1001 in binary)