# Maximum length in bits of the product n=pq

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

• You are assuming a least significant bit of zero for two (large) prime numbers? Which one of them is even? – Maarten Bodewes Nov 26 '14 at 9:37

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.

• As we are clearly talking about RSA here, it would be nice to explain how $n$ is set to be exactly the key size during key pair generation - obviously that does not lead from the $pq$ calculation in itself. – Maarten Bodewes Nov 26 '14 at 13:10
• Perfect, thanks! Cannot vote up more though :) – Maarten Bodewes Nov 26 '14 at 16:05

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).

• Partial answer at best, there were two related questions. – Maarten Bodewes Nov 26 '14 at 9:36
• @owlstead updated the answer. – Pratik Soni Nov 26 '14 at 11:11

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)

• Partial answer at best, there were two related questions. – Maarten Bodewes Nov 26 '14 at 9:37
• The assertion the total number of bits after multiplication will be 2*1024 is incorrect; counterexample: $p=q=2^{1023}+1155$. – fgrieu Nov 26 '14 at 12:18
• so there will not be a maximum of 2048 bits? – cryptoclk Nov 26 '14 at 14:38
• @fgrieu How did you find such $p, q$? – xxx--- Nov 26 '14 at 14:41
• @pushpen.paul: NextPrime[2^1023]-2^1023 is 1555 according to WolframAlpha – fgrieu Nov 26 '14 at 14:47