[boost] XInt library primality test

Subject: [boost] XInt library primality test
From: Jorge Lodos Vigil (lodos_at_[hidden])
Date: 2011-09-22 08:46:22

Hi
The recently reviewed (and rejected) XInt library includes prime number functionality. To evaluate primality it uses Miller-Rabin test iterating 5 times. For "small" primes this is way insufficient, while for "large" primes it is more than needed. This last case have an important speed impact for numbers with more than 1024 bits . In its current state the library cannot correctly evaluate primality for numbers with less than 400 bits.
You may consult "Damgaard, Landrock, Pomerance: Average case error estimates for the strong probable prime test. Math. Comp. 61 (1993)".
Additionally, it seems that efficiency may be gained using boost/math/special_functions/prime.hpp instead of calculating the first 2000 primes.
If there will be any further work on this library I'm willing to provide patches and tests.
Thank you.

Best regards
Jorge