Lucas pseudoprime

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-Wagstaff-Lucas pseudoprimes

Baillie and Wagstaff define Lucas pseudoprimes as follows: Given integers P and Q, where P > 0 and <math>D=P^2-4Q</math>,

let U_k(P, Q) and V_k(P, Q) be the corresponding Lucas sequences.

Let n be a positive integer and let <math>\left(\tfrac{D}{n}\right)</math> be the Jacobi symbol. We define

: <math>\delta(n)=n-\left(\tfrac{D}{n}\right).</math>

If n is a prime that does not divide Q, then the following congruence condition holds:

If this congruence does not hold, then n is not prime.

If n is composite, then this congruence usually does not hold. pages 142–152 of the book by Crandall and Pomerance, and pages 53–74 of the book by Ribenboim.

Lucas probable primes and pseudoprimes

A Lucas probable prime for a given (P, Q) pair is any positive integer n for which equation () above is true (see, or pages 266–269 of

is a strong Lucas pseudoprime for a set of parameters (P, Q) where Q = 1, satisfying one of the conditions

:<math> U_d \equiv 0 \text{ and } V_d \equiv \pm 2 \pmod {n} </math>

or

:<math> V_{d \cdot 2^r} \equiv 0 \pmod {n} </math>

for some <math> 0 \le r < s-1</math>. An extra strong Lucas pseudoprime is also a strong Lucas pseudoprime for the same <math>(P,Q)</math> pair. No number can be a strong Lucas pseudoprime to more than of all bases, or an extra strong Lucas pseudoprime to more than of all bases.

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 <math>\left(\tfrac{D}{n}\right)=-1</math>, 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 <math>\left(\tfrac{D}{n}\right)=-1</math>. Note that <math>\left(\tfrac{k}{n}\right)\left(\tfrac{-k}{n}\right)=-1</math>.

(If D and n have a prime factor in common, then <math>\left(\tfrac{D}{n}\right)=0.</math>).

With this sequence of D values, the average number of D values that must be tried before we encounter one whose Jacobi symbol is &minus;1 is about 1.79.

Once we have D, we set <math>P=1</math> and <math>Q=(1-D)/4</math>.

It is a good idea to check that n has no prime factors in common with P or Q.

This method ("Method A") 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 <math>U_{n+1}</math> and <math>V_{n+1}</math> in <math>O(\log_2 n)</math> steps; see . To start off,

:<math>U_1=1</math>

:<math>V_1=P</math>

:<math>Q^1=Q</math>

First, we can double the subscript from <math>k</math> to <math>2k</math> in one step using the recurrence relations

:<math>U_{2k}=U_k\cdot V_k,</math>

:<math>V_{2k}=V_k^2-2Q^k=\frac{V_k^2+DU_k^2}{2},</math>

:<math>Q^{2k}=(Q^k)^2.</math>

Next, we can increase the subscript by 1 using the recurrences

:<math>U_{2k+1}=(P\cdot U_{2k}+V_{2k})/2,</math>

:<math>V_{2k+1}=(D\cdot U_{2k}+P\cdot V_{2k})/2,</math>

:<math>Q^{2k+1}=Q\cdot Q^{2k}.</math>

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: 1₂ = 1, 10₂ = 2, 100₂ = 4, 101₂ = 5, 1010₂ = 10, 1011₂ = 11, 10110₂ = 22, 101100₂ = 44. Therefore, we compute U₁, U₂, U₄, U₅, U₁₀, U₁₁, U₂₂, and U₄₄. We also compute the same-numbered terms in the V sequence, along with Q¹, Q², Q⁴, Q⁵, Q¹⁰, Q¹¹, Q²², and Q⁴⁴.

By the end of the calculation, we will have computed U_n+1, V_n+1, and Qⁿ⁺¹, (mod n).

We then check congruence () using our expected value of U_n+1.

When the parameters D, P, and Q are chosen as described above, the first 10 Lucas pseudoprimes are:

323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179, and 10877

The strong versions of the Lucas test can be implemented in a similar way. With the same parameters, the first 10 strong Lucas pseudoprimes are: 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519

Extra strong Lucas pseudoprimes use different parameters: fix <math>Q = 1</math>.

Then try P = 3, 4, 5, 6, ..., until a value of <math>D=P^2-4Q</math> is found so that the Jacobi symbol <math>\left(\tfrac{D}{n}\right)=-1</math>. The first 10 extra strong Lucas pseudoprimes are

989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, and 72389

Checking additional congruence conditions

If we have checked that congruence () 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.

If n is an odd prime and <math>\left(\tfrac{D}{n}\right)=-1</math>, then we have the following:

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 U_n+1 is to compute V_n+1 as well.

If Selfridge's Method A (above) for choosing parameters is modified so that, if it selects D = 5, it uses the parameters P = Q = 5 rather than P = 1, Q = −1 (avoiding Q ≠ ±1; "Method A*"), then 913 = 11·83 is the only composite less than 10⁸ for which congruence () is true (see page 1409 and Table 6 of;

If <math>Q \neq \pm 1 </math> (and GCD(n, Q) = 1), then an Euler–Jacobi probable prime test to the base Q can also be implemented at minor computational cost.

The computation of <math>V_{n+1}</math> depends on <math>V_{(n+1)/2}</math> and <math>Q^{(n+1)/2}</math>. This is <math>Q</math> times <math>Q^{(n-1)/2}</math>, and if n is prime, then by Euler's criterion,

:<math> Q^{(n-1)/2} \equiv \left(\tfrac{Q}{n}\right) \pmod {n} </math> .

(Here, <math>\left(\tfrac{Q}{n}\right)</math> is the Legendre symbol; if n is prime, this is the same as the Jacobi symbol).

Therefore, if n is prime, we must have,

The Jacobi symbol on the right side is easy to compute, so this congruence is easy to check.

If this congruence does not hold, then n cannot be prime. Provided GCD(n, Q) = 1 then testing for congruence () is equivalent to augmenting our Lucas test with a "base Q" Solovay–Strassen primality test.

There is one more<!--There are two conditions, equations (3) and (4) from the paper, but if the V_{n+1} condition (2) is true, then they are equivalent.--> congruence condition on <math>U_n</math> and <math>V_n</math> which must be true if n is prime and can be checked.

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)^k.

There is a similar probability estimate for the strong Lucas probable prime test.

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)^k.

There are two trivial exceptions. One is n = 9. The other is when n = p(p+2) is the product of two twin primes. Such an n is easy to factor, because in this case, n+1 = (p+1)² 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.

Fibonacci pseudoprimes

When P = 1 and Q = &minus;1, the U_n(P,Q) sequence represents the Fibonacci numbers.

A Fibonacci pseudoprime is often

: a Fibonacci pseudoprime is a composite number n for which congruence () holds with P = 1 and Q = &minus;1.

This definition leads the Fibonacci pseudoprimes form a sequence:

: 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251, ... ,

which are also referred to as Bruckman-Lucas pseudoprimes. Singmaster computed these pseudoprimes up to 100000. Jacobsen lists all 111443 of these pseudoprimes less than 10¹³.

It has been shown that there are no even Fibonacci pseudoprimes as defined by equation (5). However, even Fibonacci pseudoprimes do exist under the first definition given by ().

A strong Fibonacci pseudoprime is a composite number n for which congruence () holds for Q = &minus;1 and all P. It follows