4
$\begingroup$

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?

  • 0
    Please see the update in my post.2011-05-25

2 Answers 2

3

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.

  • 0
    @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.2011-05-28
3

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.

  • 0
    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.2011-05-08