XInt library primality test
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
On Thu, 22 Sep 2011 12:46:22 +0000 Jorge Lodos Vigil <lodos@segurmatica.cu> 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. * * *
Chad Nelson wrote:
On Thu, 22 Sep 2011 12:46:22 +0000 Jorge Lodos Vigil <lodos@segurmatica.cu> 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
On Fri, 23 Sep 2011 14:48:48 +0000 Jorge Lodos Vigil <lodos@segurmatica.cu> wrote:
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.
Ah, I see. That would be slightly more processor-efficient, but slightly less efficient in terms of program size. Since they can be easily and quickly calculated and cached, I prefer to go that route.
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.
Thanks. I have a copy of that, I'll take a look once I can get back to XInt. -- Chad Nelson Oak Circle Software, Inc. * * *
participants (2)
-
Chad Nelson -
Jorge Lodos Vigil