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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk