Editing Primality test (section)

== 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 primality test]] and the Fibonacci test are simple examples, and they are 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:
* 2<sup>''p''−1</sup> ≡ 1 (mod ''p''),
* ''f''<sub>''p''+1</sub> ≡ 0 (mod ''p''),
where ''f<sub>k</sub>'' is the ''k''-th [[Fibonacci number]]. The first condition is the Fermat primality test using base 2.

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

* 2<sup>''p''−1</sup> ≡ 1 (mod ''p''),
* ''f''(''1'')<sub>''p''+1</sub> ≡ 0 (mod ''p''),

''f''(''x'')<sub>''k''</sub> is the ''k''-th [[Fibonacci polynomial]] at ''x''.

Selfridge, [[Carl Pomerance]] and [[Samuel Wagstaff]] together offer $620 for a counterexample.<ref>[[John Selfridge#Selfridge's conjecture about primality testing]].</ref>