information:filtering, structural:reformatting, structural:summarization, linguistic:translation
Heuristic tests

These are tests that seem to work well in practice, but are unproven and therefore are not, technically speaking, algorithms at all.The Fermat test and the Fibonacci test are simple examples, and they are very effective when combined. John Selfridge has conjectured that if p is an odd number, and p ≡ ±2 (mod 5), then p will be prime if both of the following hold:

where f is the k -th Fibonacci number. The first condition is the Fermat primality test using base 2.

In general, if p ≡ a (mod x +4), where a is a quadratic non-residue (mod x +4) then p should be prime if the following conditions hold:

f (x) is the k -th Fibonacci polynomial at x.

Selfridge, Carl Pomerance, and Samuel Wagstaff together offer $620 for a counterexample.