Boost logo

Boost :

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 has valuable information about prime number generation.
Note that the random number used in Miller-Rabin must be k-bit.
Thank you.

Best regards

Boost list run by bdawes at, gregod at, cpdaniel at, john at