Re: [boost] XInt library primality test

Subject: Re: [boost] XInt library primality test
From: Jorge Lodos Vigil (lodos_at_[hidden])
Date: 2011-09-23 10:48:48

Chad Nelson wrote:

> On Thu, 22 Sep 2011 12:46:22 +0000
> Jorge Lodos Vigil <lodos_at_[hidden]> wrote:

>> Additionally, it seems that efficiency may be gained using 
>> boost/math/special_functions/prime.hpp instead of calculating the 
>> first 2000 primes.

>(One point: it's using the prime numbers less than 2000, not the first 2000 of them. I don't recall how many that came out to.)

>There *is* apparently a more efficient algorithm for that ("using a wheel"), but I'm not familiar with it yet. Is that what you're referring to?

No, I was referring to static lists of prime numbers already calculated and stored.
Chapter 4 of "Handbook of Applied Cryptography" by A. Menezes, P. van Oorschot and S. Vanstone available in http://www.cacr.math.uwaterloo.ca/hac/ has valuable information about prime number generation. 
Note that the random number used in Miller-Rabin must be k-bit.
Thank you.

Best regards
Jorge