# Why should the factors $p,q$ of $n$ be half the bit length of $n$ in RSA?

Why do we want the factors $p,q$ of $n$ to be of size half the bit length of $n$ in RSA?

I know $p,q$ need to be large so that it is harder to factor $n$ and if one of $p,q$ is small, then it is more likely to find a factorization by brute force. But why half the bits of $n$ (i.e., $p,q$ must be in range $[2^{(n-1)/2} \dots 2^{n/2}]$)? Is it just that for $p,q$ to be the largest possible they both need to be of size half the bit length of $n$?

• Where did you read this or who told you that? Can you add a source for your information. Nov 27 '17 at 12:27

They don't need to be restricted to that range. It's just a safe and convenient choice with no downsides.

• Having a small p or q enables easier factorization using the elliptic curve method. To avoid ECM being faster than GNFS you need the primes to be larger than about 30% of the modulus (depends on the key size).
• Having a large p or q reduces performance, because the Chinese remainder theorem based speedup becomes less efficient.
• Having a nice power-of-two size for both factors is convenient for the implementer, especially in hardware
• If you restrict them to the range $[2^{(n-1)/2} ... 2^{n/2}]$, you get the nice property that you can generate p and q independently and get modulus of exactly the desired size.
• It only marginally reduces the number of available primes, which has no security impact.

Personally I'd go even one step further and restrict to $[\frac{3}{4} \cdot 2^{n/2} ... 2^{n/2}]$ because it simplifies key generation (just set the two most significant bits to 1)