Thanks and with respect to the users of this site, I've succeeded in creating an Encryption/Decryption procedure for the RSA algorithm.

I also implemented a Miller-Rabin probabilistic primality test.

Now my question is much simpler, but my head really cannot make up an answer.

Suppose I need a key of length 1024, and I've generated two primes, each 512 bits worth. But their product won't necessarily be 1024-bit long, it may be smaller.

What should I do in this case? Discard the primes and try again? Is there a smarter solution?

Thank you very much!

============ UPDATE ===================

Thanks to jug and Gadi A, I've managed to learn that for binary numbers, setting two most significant bits to 1 is enough to gen desired bit-length.

Another challenge is that in my library big numbers may have arbitrary digit base;

So the actual structure is a_0 mod BASE | a_1 mod BASE | ... | a_(n-1) mod BASE.

What should I do in order to get a key of n digits length, where all digits have numeric base BASE?

  • 2
    $\begingroup$ Choose the highest two bits of both numbers to be 11. $\endgroup$ – j.p. May 6 '11 at 10:09
  • $\begingroup$ Please see the update in my post. $\endgroup$ – wh1t3cat1k May 25 '11 at 17:08

I guess your updated question is: How can I generate two n-digit primes (in base $b$) such that their product has 2n digits?

One way: Have both of them greater than $\sqrt{b^{2n-1}}$. (Then their product is greater than $b^{2n-1}$ and thus has 2n digits.) You will still have a large region in which you can randomly generate the primes. For instance, to generate two 2-digit primes in base 10 whose product has 4 digits, you just have to make sure that they are both at least 32. (Since $\sqrt{1000}\approx31.6$.)

More simply, if you don't want to calculate $\sqrt{b^{2n-1}} = (\sqrt{b})b^{n-1}$ precisely, you can just make sure that the first digit of the primes is something at least $\sqrt{b}$. Thus for instance, when generating two n-digit primes in base 10, just make sure that the first digit of both primes is at least 4. (Since $\sqrt{10}\approx3.16$.) This would mean that each prime is at least $\sqrt{b}b^{n-1}$ as before, thus their product is at least $b^{2n-1}$ and has $2n$ digits.

  • $\begingroup$ The last paragraph is of course just a special case of the previous case; if you calculate √b to k digits, just set the first k digits greater than that. $\endgroup$ – ShreevatsaR May 26 '11 at 3:00
  • $\begingroup$ I couldn't quite understand if this was a little mistake: $BASE^{2n+1}$ actually has to have at least $2n+2$ digits, as, e.g. $10^2$ has $2+1=3$ digits of length in base 10. Also, could you please add a few words of explanation for the dumb - why the second paragraph' method would work? "At least $\sqrt(b)$" - did you mean "more" or am I wrong again? Sorry for such questions, I really want to understand the case, not just hard-code it) $\endgroup$ – wh1t3cat1k May 28 '11 at 19:16
  • $\begingroup$ @wh1t3cat1k: Sorry, (2n+1) should have been (2n-1); I've fixed it. And note that "an integer at least 31.6" is the same as "an integer more than 31.6" — both actually mean "at least 32". So if your base is not a square (i.e. $\sqrt{b}$ is not an integer), you can interpret "at least" above as "more than". In any case, it's safe to use "more" instead of "at least"; your region will still be large enough. $\endgroup$ – ShreevatsaR May 28 '11 at 20:27

You should simply pick the numbers at random in a way that ensures they are larger from some big number; it can be done by setting the MSB to be 1, as was suggested in the comment. You can also do something like

p=rand(big_num) + big_num;

One additional tip - most of the time you won't need Miller-Rabin to discover that a random number is not a prime - keep a table of the first 100 primes or so and attempt to divide the number you're testing by them first. It usually saves a lot of time in practice.

  • $\begingroup$ Gadi A - what is that: p=rand(big_num) + big_num;. I'm sorry I can't quite get it. $\endgroup$ – wh1t3cat1k May 6 '11 at 12:52
  • $\begingroup$ A pseudocode; What language are you using? $\endgroup$ – Gadi A May 6 '11 at 13:41
  • $\begingroup$ It's not enough to set the MSB to $1$ -- the product of two $n$-bit numbers is either $2n$ or $2n-1$ bits, and the OP needs a $2n$-bit product. You have to set the top two bits to $1$, as jug said. $\endgroup$ – TonyK May 6 '11 at 15:11
  • $\begingroup$ Gadi A, I am using C#. Thank you for the answer! Another problem is that my numbers may have arbitrary digit base. I'll edit my question in order to reflect the problem instead of asking a new one. $\endgroup$ – wh1t3cat1k May 8 '11 at 8:25

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.