Re: [boost] XInt library primality test

Subject: Re: [boost] XInt library primality test
From: Chad Nelson (chad.thecomfychair_at_[hidden])
Date: 2011-09-23 08:36:54

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

> 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 .

Hm... I see, you're right. I was relying on the guidance of Applied
Cryptography, Second Edition, which is geared explicitly toward primes
of cryptographic length. A general math library needs something smarter.

> 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)".

Thanks. I hadn't read that one myself, though Applied Cryptography does
cite it. According to the algorithm described there (and if I'm
calculating it right), a random 100-bit composite number has
approximately a one in 1200 chance of slipping through five iterations
of that test, which is definitely way too low.

> 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?

> If there will be any further work on this library I'm willing to
> provide patches and tests. Thank you.

I'm planning to continue working on it, but I can't spare the time to
do so for at least the next few months (gotta concentrate on paying
work for the next little while). I will gladly accept patches and tests
for it though.
-- 
Chad Nelson
Oak Circle Software, Inc.
*
*
*