Editing Lucas pseudoprime (section)

== Comparison with the Miller–Rabin primality test ==

''k'' applications of the [[Miller–Rabin primality test]] declare a composite ''n'' to be probably prime with a probability at most (1/4)<sup>''k''</sup>.

There is a similar probability estimate for the strong Lucas probable prime test.<ref>{{cite journal|title=The Rabin-Monier Theorem for Lucas Pseudoprimes|journal=Mathematics of Computation|date=April 1997|volume=66|issue=218|pages=869–881|author=F. Arnault|doi=10.1090/s0025-5718-97-00836-3|citeseerx=10.1.1.192.4789}}</ref>

Aside from two trivial exceptions (see below), the fraction of (''P'',''Q'') pairs (modulo ''n'') that declare a composite ''n'' to be probably prime is at most (4/15).

Therefore, ''k'' applications of the strong Lucas test would declare a composite ''n'' to be probably prime with a probability at most (4/15)<sup>k</sup>.

There are two trivial exceptions. One is ''n'' = 9. The other is when ''n'' = ''p''(''p''+2) is the product of two [[twin prime]]s. Such an ''n'' is easy to factor, because in this case, ''n''+1 = (''p''+1)<sup>2</sup> is a perfect square. One can quickly detect perfect squares using [[Newton's method]] for square roots.

By combining a Lucas pseudoprime test with a [[Fermat primality test]], say, to base 2, one can obtain very powerful probabilistic tests for primality, such as the [[Baillie–PSW primality test]].