Optimal number of times for value to be tested using Fermat primality test

[arafel]

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.

[Tedd]

I would assume you have to do more tests as the numbers get bigger.
Try to find a nice percentage for smaller numbers, and then see how that translates for the bigger numbers.

[arafel]

Yes, but unfortunately I haven't managed to find yet any relation (that seems constant for different ranges) of percentage between small numbers and bigger ones.

It's very surprising that there is not much info available on this. Knowing the optimal number of times a prime candidate should be tested for a particular range could increase the speed dramatically and yet have zero failure rate for determining a pseudoprime.

[Eddy]

Fermats little theorem is a probabilistic test. This means that, if Fermat says 'not prime', you can be sure that the number is not a prime. On the other hand, if it says 'prime', there is always a chance that the number is composite (not prime).
The more tests you perform (with different bases), the higher the chance that Fermat is correct. The number of tests you have to perform does not depend on the size of the number. In fact, there is a type of composite numbers, called Carmichael numbers that can not be detected with Fermat as non-primes.!
The Rabin-Miller prime testing algorithm can! But also only with a large enough number of tests, like 50 ...

To save time, you could test a number with only a few tests (2 or 3). If Fermat says 'prime' you could do another test with a much higher number of tests, like 30-40.

Kind regards
Eddy
www.devotechs.com

[arafel]

The number of tests you have to perform does not depend on the size of the number.

From a few test I have done, it looks more like the opposite. Small number require less tests while bigger more. I haven't managed to find any correlation between different ranges though.

In fact, there is a type of composite numbers, called Carmichael numbers that can not be detected with Fermat as non-primes.!
The Rabin-Miller prime testing algorithm can!

Carmichael numbers are entirely different subject from what I was talking about.

To save time, you could test a number with only a few tests (2 or 3). If Fermat says 'prime' you could do another test with a much higher number of tests, like 30-40.

That is one approach. Another way would be to know an approximate number of tests for a particular range and test accordingly.

[Tedd]

I would be tempted to test against the first 100 primes (quick to find by exact methods) and then test further by other methods if needed ( > 10000; and not eliminated yet.) This will eliminate many of the numbers quickly.

[Eddy]

Another way would be to know an approximate number of tests for a particular range and test accordingly.

I probably should have stated this specifically in my previous post, but as far as I know, such a correlation does not exist. Otherwise, everybody would be using it ...

Kind regards
Eddy

[arafel]

Eddy, you are probably right...

[raymond]

If it's for Project Euler,  :green2:dance: :dance: :dance:
you can't afford to be wrong in the slightest,  :snooty: and you may be wasting a lot of time and effort.

Raymond

[arafel]

Nah, I already solved almost all prime-number related problems on the project Euler  :green

[Eddy]

Arafel,
Just out of curiosity. What are you using these prime numbers for? And what size prime numbers are you calculating?

Kind regards
Eddy
www.devotechs.com

[arafel]

Eddy, I was going through my algos collection recently, stumbled upon this one and merely tried to improve it. At the moment it doesn't have any particular use other than taking space on the hd  :8)

Size of primes is limited to max. 64bit value due to algorithm limitations.

[aaustin]

The problem with Fermat testing is that some composite numbers will never be detected composite using Fermat's Method (Carmichael numbers). I would use Rabin-Miller primality test instead. It takes roughly the same amount of time as Fermat's Method, is very similar, but it has no Carmichael numbers. Assuming the Reimann Hypothesis, this algorithm would take less than:

4*70*lg(n)*ln^2(n) large integer multiplications (plus some other insignificant mathematical operations)

To Prove a number is prime. This is actually faster than deterministic AKS type algorithms.