2
$\begingroup$

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

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Nov 26 '14 at 13:10
  • $\begingroup$ Perfect, thanks! Cannot vote up more though :) $\endgroup$ – Maarten Bodewes Nov 26 '14 at 16:05
4
$\begingroup$

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

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

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)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.