1
$\begingroup$

Is it necessary to take the same bit size of "p" and "q" in case of RSA algorithm? i had read that bitsize of p and q must be same. BUT after calculating, i found that bit size could be different also. But time complexity will increase. Can anyone help me?

$\endgroup$
7
$\begingroup$

The RSA method works regardless of the size of the individual primes $p,q$. The reason that we would want $p$ and $q$ to be of roughly equal size is that one method of breaking RSA is factoring $n = pq$, and the running time of some factoring methods (notably ECM, the elliptic curve method) depends on the size of the smallest prime factor of $n$. Therefore to get the most "bang for the buck", you would like $p,q$ to be both as large as possible under the constraint on the size of $n$ (which determines the speed of encryption and decryption), and so of roughly equal size.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I think it is not required to same bit size but sufficiently large to solve it via factoring it.

Since, anyone knows n = pq, prime factor of n can be found to calculate its private key. If your q is too small say 19, and p is very large say 1000 bits prime number, you can easily get p from n just dividing it by a small number. So, both number p and q must be sufficiently large. They cannot be exact of same size but almost equal in size. Size is too large.

| cite | improve this answer | |
$\endgroup$

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.