that the number of strong Lucas pseudoprimes not exceeding is greater than , for sufficiently large. We can set Q = −1, then and are P-Fibonacci sequence and P-Lucas sequence, the pseudoprimes can be called strong Lucas pseudoprime in base P, for example, the least strong Lucas pseudoprime with P = 1, 2, 3, ... are 4181, 169, 119, ... An extra strong Lucas pseudoprimeis a strong Lucas pseudoprime for a set of parameters (P, Q) where Q = 1, satisfying one of the conditions or for some . An extra strong Lucas pseudoprime is also a strong Lucas pseudoprime for the same pair. Implementing a Lucas probable prime test Before embarking on a probable prime test, one usually verifies that n, the number to be tested for primality, is odd, is not a perfect square, and is not divisible by any small prime less than some convenient limit. Perfect squares are easy to detect using Newton's method for square roots. We choose a Lucas sequence where the Jacobi symbol , so that δ(n) = n + 1. Given n, one technique for choosing D is to use trial and error to find the first D in the sequence 5, −7, 9, −11, ... such that . Note that . (If D and n have a prime factor in common, then ). With this sequence of D values, the average number of D values that must be tried before we encounter one whose Jacobi symbol is −1 is about 1.79; see, p. 1416. Once we have D, we set and . It is a good idea to check that n has no prime factors in common with P or Q. This method of choosing D, P, and Q was suggested by John Selfridge. (This search will never succeed if n is square, and conversely if it does succeed, that is proof that n is not square. Thus, some time can be saved by delaying testing n for squareness until after the first few search steps have all failed.) Given D, P, and Q, there are recurrence relations that enable us to quickly compute and in steps; see . To start off, First, we can double the subscript from to in one step using the recurrence relations . Next, we can increase the subscript by 1 using the recurrences . If is odd, replace it with ; this is even so