I'm organizing/participating to a programming contest:
http://www.recmath.org/contest/

Since we need to test 64 bits numbers for primality, I need a FAST ASM routine, which implements Rabin-Miller.

There is a C++ package which does that:
http://jerko.foreach.org/prime/primes.tar.gz

But I think it can be improved a lot !

Any idea/suggestion/improvement ?

Thanks !
Posted on 2005-07-08 02:49:23 by MCoder
Just a suggestion,

Why don't you use fermat's little theroem to kick out the "sure-composite" before using Rabin-Miller for the psuedo-primes. This is better because I'm sure there are definitely more composites than primes and psuedo-primes. (I think you should know that it is possible to do powers in n lg n).

PS: Your link does not work, so I am unable to look at the C++ source... Do keep up with the topic as I find it pretty interesting  ;)
Posted on 2005-07-08 06:47:35 by roticv

Just a suggestion,

Why don't you use fermat's little theroem to kick out the "sure-composite" before using Rabin-Miller for the psuedo-primes. This is better because I'm sure there are definitely more composites than primes and psuedo-primes. (I think you should know that it is possible to do powers in n lg n).

PS: Your link does not work, so I am unable to look at the C++ source... Do keep up with the topic as I find it pretty interesting  ;)


Fermat's little theorem is strictly equivalent to Miller-Rabin test, except that a lot of numbers pass this test.
These numbers are called Carmichael numbers.

I uploaded the primes source on my site:
http://euler.free.fr/contest/primes.tar.gz

I'll work onto the ASM version this week-end, but I'm open to any suggestion to improve the code (ic C, it's much harder to work with the carry).

The contest IS NOT about primality testing, but having a good routine for checking primes helps a lot  ;)

JC
Posted on 2005-07-08 07:14:49 by MCoder
Okay, after some thoughts to your problem, I think the best is to
1) Check for odd number
2) Check using fermat little theorem
3) Use Rabin-Miller

You are right that Rabin-Miller is built upon Fermat's little theorem, but you have forgotten that Rabin-Miller makes use of random number (which takes time to generate and stuff). I would suggest you just do Fermat using a small base like 2.

And you are wrong. Carmichael numbers are far rarer than prime numbers. There are only 255 Carmichael numbers less than 100,000,000. Compare that with the number of primes.

Btw Rabin-Miller has an error rate of 2^-s, where s is the number of times you literate.

Grammar mistakes
Posted on 2005-07-08 07:59:01 by roticv

Okay, after some thoughts to your problem, I think the best is to
1) Check for odd number
2) Check using fermat little theorem
3) Use Rabin-Miller

You are right that Rabin-Miller is built upon Fermat's little theorem, but you have forgotten that Rabin-Miller makes use of random number (which takes time to generate and stuff). I would suggest you just do Fermat using a small base like 2.

And you are wrong. Carmichael numbers are far rarely than prime numbers. There are only 255 Carmichael numbers less than 100,000,000. Compare that with the number of primes.

Btw Rabin-Miller has an error rate of 2^-s, where s is the number of times your literate.



In fact, you're right.
At this moment, I use a table lookup for checking primality for numbers below 10^9.
What causes problem is testing larger numbers.
I'll try to implement Fermat's little theorem for 32 bits and for 64 bits, using only one base, since I don't think using more bases would improve the accuracy.

JC
Posted on 2005-07-08 09:51:54 by MCoder
For bigger primes, you would still need to use Rabin-Miller - you can't run away from it.

For smaller primes, you can build a bit table using Sieve of Eratosthenes (storing only the odd numbers) to save space. I have some codes in C where I used a char to store values instead of using a bit table because I was too lazy to figure out how to do the bit table. You would have to precalculate and plug it into your exe to speed it up  ;) It should be faster than using a binary search on your array of primes.

Since you are going to do modular powers, this thread would be useful. http://www.asmcommunity.net/board/index.php?topic=15924.0
Posted on 2005-07-08 10:09:29 by roticv
Just to mention an URL related to optimizing this problem:

http://dennishomepage.gugs-cats.dk/IsPrimeChallenge.htm
Posted on 2005-07-10 02:39:53 by MCoder