Lucas pseudoprime

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Basic properties[edit]

Given integers P and Q, where P > 0 and D=P^2-4Q, let Uk(P, Q) and Vk(P, Q) be the corresponding Lucas sequences.

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

\delta(n)=n-\left(\tfrac{D}{n}\right).

If n is a prime such that the greatest common divisor of n and Q (that is, GCD(n, Q)) is 1, then the following congruence condition holds (see page 1391 of [1]):

 \text{  } (1) \text{     } U_{\delta(n)} \equiv 0 \pmod {n}.

If this equation does not hold, then n is not prime. If n is composite, then this equation usually does not hold (see,[1] page 1392). These are the key facts that make Lucas sequences useful in primality testing.

Some good references are chapter 8 of the book by Bressoud and Wagon (with Mathematica code),[2] pages 142-152 of the book by Crandall and Pomerance,[3] and pages 53–74 of the book by Ribenboim .[4]

Lucas probable primes and pseudoprimes[edit]

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

Riesel ([5] page 130) adds the condition that the Jacobi symbol \left(\tfrac{D}{n}\right) should be −1. This not usually part of the definition, although most implementations of the Lucas primality test (such as the Baillie-PSW primality test) specifically choose D so that \left(\tfrac{D}{n}\right)=-1. Bressoud and Wagon (,[2] pages 266-269) explain why the Jacobi symbol should be −1, as well as why one gets more powerful primality tests if Q ≠ ± 1.

A Lucas probable prime test is most useful if we choose a value of D such that the Jacobi symbol \left(\tfrac{D}{n}\right) is −1 (see page 1401 of [1] or page 1024 of [6] ).

If \left(\tfrac{D}{n}\right)=-1, then equation (1) becomes

 \text{  } (2) \text{     } U_{n+1} \equiv 0 \pmod {n}.

If congruence (2) is false, this constitutes a proof that n is composite.

If congruence (2) is true, then n is a Lucas probable prime. In this case, either n prime or it is a Lucas pseudoprime. If congruence (2) is true, then n is likely to be prime (this justifies the term probable prime), but this does not prove that n is prime. As is the case with any other probabilistic primality test, if we perform additional Lucas tests with different D, P and Q, then unless one of the tests proves that n is composite, we gain more confidence that n is prime.

Examples: If P = 1, Q = −1, and D = 5, the sequence of U's is the Fibonacci sequence: F0 = U0 = 0, F1 = U1 = 1, F2 = U2 = 1, F3 = U3 = 2, etc.

First, let n = 17. The Jacobi symbol \left(\tfrac{5}{17}\right) is −1, so δ(n) = 18. The 18th Fibonacci number is 2584 = 17·152 and we have

 U_{18} = 2584 \equiv 0 \pmod {17} .

Therefore, 17 is a Lucas probable prime for this (P, Q) pair. In this case 17 is prime, so it is not a Lucas pseudoprime.

For the next example, let n = 323. We have \left(\tfrac{5}{323}\right) = −1, and we can compute

 U_{324} \equiv 0 \pmod {323}.

However, 323 = 17·19 is not prime, so 323 is a Lucas pseudoprime for this (P, Q) pair. In fact, 323 is the smallest pseudoprime for P = 1, Q = −1.

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.

Strong Lucas pseudoprimes[edit]

Now, factor \delta(n) into the form d\cdot2^s where d is odd.

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

  U_d \equiv 0 \pmod {n}

or

  V_{d \cdot 2^r} \equiv 0 \pmod {n}

for some r < s; see page 1396 of.[1] A strong Lucas pseudoprime is also a Lucas pseudoprime (for the same (P, Q) pair), but the converse is not necessarily true. Therefore, the strong test is a more stringent primality test than equation (1).

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

  U_d \equiv 0 \pmod {n}  \text{  and  } V_d \equiv \pm 2 \pmod {n}

or

  V_{d \cdot 2^r} \equiv 0 \pmod {n}

for some r<s-1. An extra strong Lucas pseudoprime is also a strong Lucas pseudoprime for the same (P,Q) pair.

Implementing a Lucas probable prime test[edit]

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.

In this section, we will assume \left(\tfrac{D}{n}\right)=-1, 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 the Jacobi symbol \left(\tfrac{D}{n}\right) is −1. (If D and n have a factor in common, then \left(\tfrac{D}{n}\right)=0). Then set P = 1 and Q=(1-D)/4. Once we have P and Q, it is a good idea to check that n has no factors in common with P or Q.

Given D, P, and Q, there are recurrence relations that enable us to quickly compute U_{n+1} and V_{n+1} without having to compute all the intermediate terms; see Lucas sequence-Other relations. First, we can double the subscript from k to 2k in one step using the recurrence relations

U_{2k}=U_k\cdot V_k
V_{2k}=V_k^2-2Q^k.

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

U_{2k+1}=(P\cdot U_{2k}+V_{2k})/2
V_{2k+1}=(D\cdot U_{2k}+P\cdot V_{2k})/2.

(If either of these numerators is odd, we can make it be even by increasing it by n, because all of these calculations are carried out modulo n.) Observe that, for each term that we compute in the U sequence, we compute the corresponding term in the V sequence. As we proceed, we also compute powers of Q.

We use the bits of the binary expansion of n + 1, starting at the leftmost bit, to determine which terms in the U sequence need to be computed. For example, if n + 1 = 44 (= 101100 in binary), we compute U1, U2, U4, U5, U10, U11, U22, and U44. We also compute the same-numbered terms in the V sequence and those powers of Q.

By the end of the calculation, we will have computed Un+1, Vn+1, and Qn+1. We then check equation (2) using our known value of Un+1.

When D, P, and Q are chosen as described above, the first 10 Lucas pseudoprimes are (see page 1401 of [6]): 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.

When D, P, and Q are chosen as described above, the first 10 strong Lucas pseudoprimes are: 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519 (sequence A217255 in OEIS)

To calculate a list of extra strong Lucas pseudoprimes, set Q = 1. Then try P = 3, 4, 5, 6, ..., until a value of D=P^2-4Q is found so that the Jacobi symbol \left(\tfrac{D}{n}\right)=-1. With this method for selecting D, P, and Q, the first 10 extra strong Lucas pseudoprimes are 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, and 72389 (sequence A217719 in OEIS)

Checking additional congruence conditions[edit]

If we have checked that equation (2) is true, there are additional congruence conditions we can check that have almost no additional computational cost. If n happens not to be prime, these additional conditions may help discover that fact.

If n is an odd prime and \left(\tfrac{D}{n}\right)=-1, then we have the following (see equation 2 on page 1392 of [1]):

 \text{  } (3) \text{     } V_{n+1} \equiv 2 Q \pmod {n} .

Although this congruence condition is not, by definition, part of the Lucas probable prime test, it is almost free to check this condition because, as noted above, the value of Vn+1 was computed in the process of computing Un+1.

If either equation (2) or (3) is false, this constitutes a proof that n is not prime. If both of these conditions are true, then it is even more likely that n is prime than if we had checked only equation (2).

If the above method for choosing D happened to set Q = −1, then we can adjust P and Q so that D and \left(\tfrac{D}{n}\right) remain unchanged and P = Q = 5 (see Lucas sequence-Algebraic relations). If we make this adjustment, there is only one composite n < 108 for which equation (3) is true (see page 1409 and Table 6 of;[1] this n is 913 = 11·83).

Here is yet another congruence condition that is true for primes and that is trivial to check.

First, recall that Q^{n+1} is computed during the calculation of U_{n+1}. It would be easy to save the previously-computed power of Q, namely, Q^{(n+1)/2}.

Next, if n is prime, then, by Euler's criterion,

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

(Here, \left(\tfrac{Q}{n}\right) is the Legendre symbol; if n is prime, this is the same as the Jacobi symbol). Therefore, if n is prime, we must have

 \text{  } (4) \text{     } Q^{(n+1)/2} \equiv Q \cdot Q^{(n-1)/2} \equiv Q \cdot \left(\tfrac{Q}{n}\right) \pmod {n}  .

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.

Additional congruence conditions that must be satisfied if n is prime are described in Section 6 of.[1] If any of these conditions fails to hold, then we have proved that n is not prime.

Comparison with the Miller-Rabin primality test[edit]

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.[8]

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)2 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[edit]

As noted above, when P = 1 and Q = −1, the numbers in the U sequence are the Fibonacci numbers.

A Fibonacci pseudoprime is often (page 264 of,[2] page 142 of,[3] or page 127 of [4]) defined as a composite number n for which equation (1) above is true with P = 1 and Q = −1. By this definition, the first ten Fibonacci pseudoprimes are 323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, and 10877 (sequence A081264 in OEIS). More of these values, along with their factorizations, are given in the references of Anderson listed below.

If n is congruent to 2 or 3 (mod 5), then Bressoud (,[2] pages 272-273) and Crandall and Pomerance (,[3] page 143 and exercise 3.41 on page 168) point out that it is rare for a Fibonacci pseudoprime to also be a Fermat pseudoprime base 2.

If n is prime and GCD(n, Q) = 1, then (see equation 4 on page 1392 of [1]) we also have

 \text{  } (5) \text{     } V_n \equiv P \pmod {n} .

This leads to an alternate definition of Fibonacci pseudoprime that is sometimes used (see ,[9] pages 459-464). By this definition, a Fibonacci pseudoprime is a composite number n for which equation (5) is true with P = 1 and Q = −1. Using this definition, the first ten Fibonacci pseudoprimes are 2737, 4181, 5777, 6721, 10877, 13201, 15251, 29281, 34561, and 51841.

A strong Fibonacci pseudoprime may be defined as a composite number for which equation (5) holds for all P. It follows (see,[9] page 360) that in this case:

  1. An odd composite integer n is also a Carmichael number
  2. 2(pi + 1) | (n − 1) or 2(pi + 1) | (npi) for every prime pi dividing n.

The smallest example of a strong Fibonacci pseudoprime is 443372888629441 = 17·31·41·43·89·97·167·331.

It is conjectured that there are no even Fibonacci pseudoprimes.[10]

References[edit]

  1. ^ a b c d e f g h i j Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes". Mathematics of Computation 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. MR 583518. 
  2. ^ a b c d David Bressoud; Stan Wagon (2000). A Course in Computational Number Theory. New York: Key College Publishing in cooperation with Springer. ISBN 978-1-930190-10-8. 
  3. ^ a b c Richard E. Crandall; Carl Pomerance (2005). Prime numbers: A computational perspective (2nd ed.). Springer-Verlag. ISBN 0-387-25282-7. 
  4. ^ a b Paulo Ribenboim (1996). The New Book of Prime Number Records. Springer-Verlag. ISBN 0-387-94457-5. 
  5. ^ Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics 126 (2nd ed.). Birkhäuser. ISBN 0-8176-3743-5. .
  6. ^ a b Carl Pomerance; John L. Selfridge, Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·109". Mathematics of Computation 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. 
  7. ^ Jon Grantham (March 2000). "Frobenius Pseudoprimes". Mathematics of Computation 70 (234): 873–891. doi:10.1090/S0025-5718-00-01197-2. MR 1680879. 
  8. ^ F. Arnault (April 1997). "The Rabin-Monier Theorem for Lucas Pseudoprimes". Mathematics of Computation 66 (218): 869–881. 
  9. ^ a b Müller, Winfried B. and Alan Oswald. "Generalized Fibonacci Pseudoprimes and Probable Primes." In G.E. Bergum et al., eds. Applications of Fibonacci Numbers. Volume 5. Dordrecht: Kluwer, 1993.
  10. ^ Somer, Lawrence (1991). "On Even Fibonacci Pseudoprimes". In G. E. Bergum et al. Applications of Fibonacci Numbers 4. Dordrecht: Kluwer. pp. 277–288. 

External links[edit]