So I was wondering what is most efficient in sense of speed and reliability number of times a value should be tested?

For example, after some checks I have noticed that for 5 digit values it's quiet reliable and fast to check every thirteenth value in range of 1 up to our prime candidate. However values with 10 ore more digits return some noticeable amount of fermat liars in this case.
Posted on 2006-04-01 08:19:10 by arafel
Fermat liars = pseudoprimes?
Anyway, one fact for sure is that Carmichael numbers are rarer than prime numbers.

Are you using Miller-Rabin?

According to CLR (I don't have CLRS), Theorem 33.39 states that for any odd interger n > 2and positive integer s, the probability that Miller-Rabin(n,s) errs is at most 2^-s.
Posted on 2006-04-01 20:42:36 by roticv

Fermat liars = pseudoprimes?


I am not using Miller-Rabin, but instead it predecessor, simple primality test based upon Fermat little theorem.(ie. "a^(n-1) mod n" where n is value to be tested for primality and a is a value in range 1,n-1. )

Carmichael numbers are not that much of worry to me, as after the main test I am checking the value against table of known values (currently up to 10^16)

What is CLR?
Posted on 2006-04-02 11:15:11 by arafel

Basically I am looking for info (derived from statistics or any mathematical explanation) regarding the optimal number and\or sequence of "a" values for which a value should be tested.

Currently this works for me:

((a-13)>1)^(n-1) mod n?               (with initial a=n-1)

But its inefficient to do this for every number range, as it seems clearly that some ranges require more check and some less.

Anyhow, for some reason I have suspicion there is no such information currently available. Just spent over a week searching the net and local library, but got nothing  :mad:
Posted on 2006-04-02 16:55:09 by arafel

Sorry for the late reply as I was stuck in the army camp - I can only come home during the weekends.

Anyway, I was thinking that you should just kick out those numbers that are definitely not a prime by runnning through with fermat's little theorem. Remember that using fermat's little theroem is only a probabilitistic test.

If it fails, then you should proceed with a deterministic primality test such as "Elliptic Curve Primality Proving" (

Or of course you can try using Miller-Rabin.

I thought CLR is very well known. Anyway, CLR/CLRS refers to the book "Introduction to Algorithms". It is called CLR because of the surnames of the authors of that book. The authors are Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. CLRS is the second edition of that book and there is one more author which is Clifford Stein.

Posted on 2006-04-08 06:58:12 by roticv
Thanks for the tips roticv.
Posted on 2006-04-08 08:03:38 by arafel
You are welcome. I have always found anything related to prime numbers interesting (Including integer factorising).  ;)
Posted on 2006-04-08 14:01:19 by roticv