Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.
Baillie and Wagstaff define Lucas pseudoprimes as follows:[1] Given integers P and Q, where P > 0 and
[1] These are the key facts that make Lucas sequences useful in primality testing.
[4] A Lucas probable prime for a given (P, Q) pair is any positive integer n for which equation (1) above is true (see,[1] page 1398).
A Lucas pseudoprime for a given (P, Q) pair is a positive composite integer n for which equation (1) is true (see,[1] page 1391).
A Lucas probable prime test is most useful if D is chosen such that the Jacobi symbol
then equation (1) becomes If congruence (2) is false, this constitutes a proof that n is composite.
We will see below that, in order to check equation (2) for a given n, we do not need to compute all of the first n + 1 terms in the U sequence.
A strong Lucas pseudoprime for a given (P, Q) pair is an odd composite number n with GCD(n, D) = 1, satisfying one of the conditions or for some 0 ≤ r < s; see page 1396 of.
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.
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
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.
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
in one step using the recurrence relations Next, we can increase the subscript by 1 using the recurrences At each stage, we reduce all of the variables modulo n. When dividing by 2 modulo n, if the numerator is odd add n (which does not change the value modulo n) to make it even before dividing by 2.'
We use the bits of the binary expansion of n to determine which terms in the sequence to compute.
For example, if n+1 = 44 (= 101100 in binary), then, taking the bits one at a time from left to right, we obtain the sequence of indices to compute: 12 = 1, 102 = 2, 1002 = 4, 1012 = 5, 10102 = 10, 10112 = 11, 101102 = 22, 1011002 = 44.
With the same parameters, the first 10 strong Lucas pseudoprimes are: 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519 (sequence A217255 in the OEIS) Extra strong Lucas pseudoprimes use different parameters: fix
The first 10 extra strong Lucas pseudoprimes are 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, and 72389 (sequence A217719 in the OEIS) If we have checked that congruence (2) is true, there are additional congruence conditions we can check that have almost no additional computational cost.
By providing an additional opportunity for n to be proved composite, these increase the reliability of the test.
2 Although this congruence condition is not part of the Lucas probable prime test proper, it is almost free to check this condition because, as noted above, the easiest way to compute Un+1 is to compute Vn+1 as well.
More extensive calculations show that, with this method of choosing D, P, and Q, there are only five odd, composite numbers less than 1015 for which congruence (3) is true.
(and GCD(n, Q) = 1), then an Euler–Jacobi probable prime test to the base Q can also be implemented at minor computational cost.
[9] 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).
Such an n is easy to factor, because in this case, n+1 = (p+1)2 is a perfect square.
A Fibonacci pseudoprime is often[2]: 264, [3]: 142, [4]: 127 defined as a composite number n not divisible by 5 for which congruence (1) holds with P = 1 and Q = −1.
[15][16] However, even Fibonacci pseudoprimes do exist (sequence A141137 in the OEIS) under the first definition given by (1).
A strong Fibonacci pseudoprime is a composite number n for which congruence (5) holds for Q = −1 and all P.[17] It follows[17]: 460 that an odd composite integer n is a strong Fibonacci pseudoprime if and only if: The smallest example of a strong Fibonacci pseudoprime is 443372888629441 = 17·31·41·43·89·97·167·331.
This differs from the definition in OEIS: A099011 which may be written as: with (P, Q) = (2, −1) again defining Un as the Pell sequence.