Skip to main content

Lucas pseudoprime









Lucas pseudoprime


From Wikipedia, the free encyclopedia

Jump to navigation
Jump to 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.




Contents






  • 1 Bruckman-Lucas pseudoprimes


  • 2 Baillie-Wagstaff-Lucas pseudoprimes


  • 3 Lucas probable primes and pseudoprimes


  • 4 Strong Lucas pseudoprimes


  • 5 Implementing a Lucas probable prime test


    • 5.1 Checking additional congruence conditions




  • 6 Comparison with the Miller–Rabin primality test


  • 7 Fibonacci pseudoprimes


  • 8 Pell pseudoprimes


  • 9 References


  • 10 External links





Bruckman-Lucas pseudoprimes[edit]


The Lucas pseudoprimes as defined by Bruckman are as follows.[1] The Lucas numbers may be defined as:


Ln:={2if n=0;1if n=1;Ln−1+Ln−2if n>1.{displaystyle L_{n}:={begin{cases}2&{text{if }}n=0;\1&{text{if }}n=1;\L_{n-1}+L_{n-2}&{text{if }}n>1.\end{cases}}}L_{n}:={begin{cases}2&{text{if }}n=0;\1&{text{if }}n=1;\L_{n-1}+L_{n-2}&{text{if }}n>1.\end{cases}}

(where n belongs to the natural numbers). For any prime p, Lp is congruent to 1 mod p. The converse is almost always true, that is, if n is composite, Ln is not congruent to 1 mod n in most cases. The exceptions are the Bruckman-Lucas pseudoprimes, of which the first few are n = 705, 2465, 2737, 3745, 4181, 5777, 6721, ...[2]



Baillie-Wagstaff-Lucas pseudoprimes[edit]


Baillie and Wagstaff define Lucas pseudoprimes differently.[3] Given integers P and Q, where P > 0 and D=P2−4Q{displaystyle D=P^{2}-4Q}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 (Dn){displaystyle left({tfrac {D}{n}}right)}left({tfrac {D}{n}}right) be the Jacobi symbol. We define


δ(n)=n−(Dn).{displaystyle delta (n)=n-left({tfrac {D}{n}}right).}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:








Uδ(n)≡0(modn).{displaystyle U_{delta (n)}equiv 0{pmod {n}}.}{displaystyle U_{delta (n)}equiv 0{pmod {n}}.}









 

 

 

 

(1)


If this equation does not hold, then n is not prime.
If n is composite, then this equation usually does not hold.[3] 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),[4] pages 142–152 of the book by Crandall and Pomerance,[5] and pages 53–74 of the book by Ribenboim.[6]



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,[3] page 1398).


A Lucas pseudoprime for a given (P, Q) pair is a positive composite integer n for which equation (1) is true (see,[3] page 1391).


A Lucas probable prime test is most useful if D is chosen such that the Jacobi symbol (Dn){displaystyle left({tfrac {D}{n}}right)}left({tfrac {D}{n}}right) is −1
(see pages 1401–1409 of,[3] page 1024 of
,[7] or pages 266–269 of [4]
). This is especially important when combining a Lucas test with a strong pseudoprime test, such as the Baillie-PSW primality test. Typically implementations will use a parameter selection method that ensures this condition (e.g. the Selfridge method recommended in [3] and described below).


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








Un+1≡0(modn).{displaystyle U_{n+1}equiv 0{pmod {n}}.}{displaystyle U_{n+1}equiv 0{pmod {n}}.}









 

 

 

 

(2)


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 is 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 = 3, Q = −1, and D = 13, the sequence of U's is OEIS: A006190: U0 = 0, U1 = 1, U2 = 3, U3 = 10, etc.


First, let n = 19. The Jacobi symbol (1319){displaystyle left({tfrac {13}{19}}right)}left({tfrac {13}{19}}right) is −1, so δ(n) = 20, U20 = 6616217487 = 19·348221973 and we have


U20=6616217487≡0(mod19).{displaystyle U_{20}=6616217487equiv 0{pmod {19}}.}U_{20}=6616217487equiv 0{pmod {19}}.

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


For the next example, let n = 119. We have (13119){displaystyle left({tfrac {13}{119}}right)}left({tfrac {13}{119}}right) = −1, and we can compute


U120≡0(mod119).{displaystyle U_{120}equiv 0{pmod {119}}.}U_{120}equiv 0{pmod {119}}.

However, 119 = 7·17 is not prime, so 119 is a Lucas pseudoprime for this (P, Q) pair.
In fact, 119 is the smallest pseudoprime for P = 3, 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.


Let Q = −1, the smallest Lucas pseudoprime to P = 1, 2, 3, ... are


323, 35, 119, 9, 9, 143, 25, 33, 9, 15, 123, 35, 9, 9, 15, 129, 51, 9, 33, 15, 21, 9, 9, 49, 15, 39, 9, 35, 49, 15, 9, 9, 33, 51, 15, 9, 35, 85, 39, 9, 9, 21, 25, 51, 9, 143, 33, 119, 9, 9, 51, 33, 95, 9, 15, 301, 25, 9, 9, 15, 49, 155, 9, 399, 15, 33, 9, 9, 49, 15, 119, 9, ...


Strong Lucas pseudoprimes[edit]


Now, factor δ(n)=n−(Dn){displaystyle delta (n)=n-left({tfrac {D}{n}}right)}{displaystyle delta (n)=n-left({tfrac {D}{n}}right)} into the form d⋅2s{displaystyle dcdot 2^{s}}dcdot 2^{s} where d{displaystyle d}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


Ud≡0(modn){displaystyle U_{d}equiv 0{pmod {n}}}U_{d}equiv 0{pmod {n}}

or


Vd⋅2r≡0(modn){displaystyle V_{dcdot 2^{r}}equiv 0{pmod {n}}}V_{dcdot 2^{r}}equiv 0{pmod {n}}

for some 0 ≤ r < s; see page 1396 of.[3] 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).


We can set Q = −1, then Un{displaystyle U_{n}}U_{n} and Vn{displaystyle V_{n}}V_{n} 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 323, 169, 119, ...


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


Ud≡0(modn) and Vd≡±2(modn){displaystyle U_{d}equiv 0{pmod {n}}{text{ and }}V_{d}equiv pm 2{pmod {n}}}U_{d}equiv 0{pmod {n}}{text{ and }}V_{d}equiv pm 2{pmod {n}}

or


Vd⋅2r≡0(modn){displaystyle V_{dcdot 2^{r}}equiv 0{pmod {n}}}V_{dcdot 2^{r}}equiv 0{pmod {n}}

for some 0≤r<s−1{displaystyle 0leq r<s-1}{displaystyle 0leq r<s-1}. An extra strong Lucas pseudoprime is also a strong Lucas pseudoprime for the same (P,Q){displaystyle (P,Q)}(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. Perfect squares are easy to detect using Newton's method for square roots.


We choose a Lucas sequence where the Jacobi symbol (Dn)=−1{displaystyle left({tfrac {D}{n}}right)=-1}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 (Dn){displaystyle left({tfrac {D}{n}}right)}left({tfrac {D}{n}}right) is −1.
(If D and n have a prime factor in common, then (Dn)=0{displaystyle left({tfrac {D}{n}}right)=0}left({tfrac {D}{n}}right)=0).
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,[3] p. 1416.
Once we have D, we set P = 1 and Q=(1−D)/4{displaystyle Q=(1-D)/4}Q=(1-D)/4.
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 Un+1{displaystyle U_{n+1}}U_{{n+1}} and Vn+1{displaystyle V_{n+1}}V_{{n+1}} in O(log2⁡n){displaystyle O(log _{2}n)}{displaystyle O(log _{2}n)} steps; see Lucas sequence § Other relations. First, we can double the subscript from k{displaystyle k}k to 2k{displaystyle 2k}2k in one step using the recurrence relations



U2k=Uk⋅Vk{displaystyle U_{2k}=U_{k}cdot V_{k}}U_{2k}=U_{k}cdot V_{k}


V2k=Vk2−2Qk{displaystyle V_{2k}=V_{k}^{2}-2Q^{k}}V_{2k}=V_{k}^{2}-2Q^{k}.


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



U2k+1=(P⋅U2k+V2k)/2{displaystyle U_{2k+1}=(Pcdot U_{2k}+V_{2k})/2}U_{{2k+1}}=(Pcdot U_{{2k}}+V_{{2k}})/2


V2k+1=(D⋅U2k+P⋅V2k)/2{displaystyle V_{2k+1}=(Dcdot U_{2k}+Pcdot V_{2k})/2}V_{{2k+1}}=(Dcdot U_{{2k}}+Pcdot 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 the same, corresponding 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), then, using these bits from left to right, we compute U1, U2, U4, U5, U10, U11, U22, and U44. We also compute the same-numbered terms in the V sequence, along with Q1, Q2, Q4, Q5, Q10, Q11, Q22, and Q44.


By the end of the calculation, we will have computed Un+1, Vn+1, and Qn+1.
We then check congruence (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 [3]):
323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179, and 10877 (sequence A217120 in the OEIS)


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 the 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=P2−4Q{displaystyle D=P^{2}-4Q}D=P^{2}-4Q is found so that the Jacobi symbol (Dn)=−1{displaystyle left({tfrac {D}{n}}right)=-1}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 the OEIS)



Checking additional congruence conditions[edit]


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


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








Vn+1≡2Q(modn).{displaystyle V_{n+1}equiv 2Q{pmod {n}}.}{displaystyle V_{n+1}equiv 2Q{pmod {n}}.}









 

 

 

 

(3)


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 congruence (2) or (3) is false, this constitutes a proof that n is not prime.
If both of these congruences are true, then it is even more likely that n is prime than if we had checked only congruence (2).


If Selfridge's method (above) for choosing D, P, and Q happened to set Q = −1, then we can adjust P and Q so that D and (Dn){displaystyle left({tfrac {D}{n}}right)}left({tfrac {D}{n}}right) remain unchanged and P = Q = 5 (see Lucas sequence-Algebraic relations).
If we use this enhanced method for choosing P and Q, then 913 = 11·83 is the only composite less than 108 for which congruence (3) is true (see page 1409 and Table 6 of;[3]).


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


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


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



Q(n−1)/2≡(Qn)(modn){displaystyle Q^{(n-1)/2}equiv left({tfrac {Q}{n}}right){pmod {n}}}Q^{(n-1)/2}equiv left({tfrac {Q}{n}}right){pmod {n}} .

(Here, (Qn){displaystyle left({tfrac {Q}{n}}right)}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



 (4) Q(n+1)/2≡Q⋅Q(n−1)/2≡Q⋅(Qn)(modn){displaystyle {text{ }}(4){text{ }}Q^{(n+1)/2}equiv Qcdot Q^{(n-1)/2}equiv Qcdot left({tfrac {Q}{n}}right){pmod {n}}}{text{ }}(4){text{ }}Q^{(n+1)/2}equiv Qcdot Q^{(n-1)/2}equiv Qcdot 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.[3] 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.[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).


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,[4] page 142 of,[5] or
page 127 of [6])
defined as a composite number n for which equation (1) above is true with P = 1 and Q = −1 (but n is not divisible by 5). By this definition, the first ten Fibonacci pseudoprimes are 323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, and 10877 (sequence A081264 in the OEIS). The references of Anderson and Jacobsen below use this definition.


If n is congruent to 2 or 3 (mod 5), then Bressoud (,[4] pages 272–273) and Crandall and Pomerance (,[5] 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. However, when n is congruent to 1 or 4 (mod 5), the opposite is true, with over 12% of Fibonacci pseudoprimes under 1011 also being base-2 Fermat pseudoprimes.


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


 (5) Vn≡P(modn).{displaystyle {text{ }}(5){text{ }}V_{n}equiv P{pmod {n}}.}{text{ }}(5){text{ }}V_{n}equiv P{pmod {n}}.

This leads to an alternate definition of Fibonacci pseudoprime.[10]
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 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, and 15251 ([6] page 129) (sequence A005845 in the OEIS).


It has been shown that there are no even Fibonacci pseudoprimes with the second definition using equation (5).[11] Using the more common first definition with equation (1), they do exist (sequence A141137 in the OEIS).


A strong Fibonacci pseudoprime may be defined as a composite number for which equation (5) holds for all P.[12] It follows ([12] page 460) that an odd composite integer is a strong Fibonacci pseudoprime if and only if:




  1. n is also a Carmichael number

  2. 2(pi + 1) | (n − 1) or 2(pi + 1) | (n − pi) for every prime pi dividing n.


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



Pell pseudoprimes[edit]


A Pell pseudoprime may be defined as a composite number n for which equation (1) above is true with P = 2 and Q = −1; the sequence Un then being the Pell sequence. The first pseudoprimes are then 35, 169, 385, 779, 899, 961, 1121, 1189, 2419, ...


This differs from the definition in OEIS: A099011 which may be written as:


 Un≡(2n)(modn){displaystyle {text{ }}U_{n}equiv left({tfrac {2}{n}}right){pmod {n}}}{text{ }}U_{n}equiv left({tfrac {2}{n}}right){pmod {n}}

with (P, Q) = (2, −1) again defining Un as the Pell sequence. The first pseudoprimes are then 169, 385, 741, 961, 1121, 2001, 3827, 4879, 5719, 6215 ...


A third definition uses equation (5) with (P, Q) = (2, −1), leading to the pseudoprimes 169, 385, 961, 1105, 1121, 3827, 4901, 6265, 6441, 6601, 7107, 7801, 8119, ...



References[edit]





  1. ^ P. S. Bruckman (1994). "Lucas Pseudoprimes are odd". Fibonacci Quarterly. 32: 155–157..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}


  2. ^ Sloane, N. J. A. (ed.). "Sequence A005845 (Bruckman-Lucas pseudoprimes)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.


  3. ^ abcdefghijklm Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. JSTOR 2006406. MR 0583518.


  4. ^ abcd
    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.


  5. ^ abc
    Richard E. Crandall; Carl Pomerance (2005). Prime numbers: A computational perspective (2nd ed.). Springer-Verlag. ISBN 0-387-25282-7.


  6. ^ abc
    Paulo Ribenboim (1996). The New Book of Prime Number Records. Springer-Verlag. ISBN 0-387-94457-5.


  7. ^ Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·109" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. JSTOR 2006210.


  8. ^ Jon Grantham (March 2000). "Frobenius Pseudoprimes". Mathematics of Computation. 70 (234): 873–891. doi:10.1090/S0025-5718-00-01197-2. MR 1680879.


  9. ^ F. Arnault (April 1997). "The Rabin-Monier Theorem for Lucas Pseudoprimes". Mathematics of Computation. 66 (218): 869–881. doi:10.1090/s0025-5718-97-00836-3.


  10. ^ Di Porto, Adina; Filipponi, Piero; Montolivo, Emilio (1990). "On the generalized Fibonacci pseudoprimes". Fibonacci Quarterly. 28: 347–354. CiteSeerX 10.1.1.388.4993.


  11. ^ Di Porto, Adina (1993). "Nonexistence of Even Fibonacci Pseudoprimes of the First Kind". Fibonacci Quarterly. 31: 173–177. CiteSeerX 10.1.1.376.2601.


  12. ^ ab Müller, Winfried B.; Oswald,Alan (1993). "Generalized Fibonacci Pseudoprimes and Probable Primes". In G.E. Bergum; et al. Applications of Fibonacci Numbers. 5. Kluwer. pp. 459–464. doi:10.1007/978-94-011-2058-6_45.




External links[edit]



  • Anderson, Peter G. Fibonacci Pseudoprimes, their factors, and their entry points.

  • Anderson, Peter G. Fibonacci Pseudoprimes under 2,217,967,487 and their factors.

  • Jacobsen, Dana Pseudoprime Statistics, Tables, and Data (data for Lucas, Strong Lucas, AES Lucas, ES Lucas pseudoprimes below 1014; Fibonacci and Pell pseudoprimes below 1012)

  • Weisstein, Eric W. "Fibonacci Pseudoprime". MathWorld.

  • Weisstein, Eric W. "Lucas Pseudoprime". MathWorld.

  • Weisstein, Eric W. "Strong Lucas Pseudoprime". MathWorld.

  • Weisstein, Eric W. "Extra Strong Lucas Pseudoprime". MathWorld.











Retrieved from "https://en.wikipedia.org/w/index.php?title=Lucas_pseudoprime&oldid=863247702"





Navigation menu

























(window.RLQ=window.RLQ||).push(function(){mw.config.set({"wgPageParseReport":{"limitreport":{"cputime":"0.512","walltime":"0.742","ppvisitednodes":{"value":2064,"limit":1000000},"ppgeneratednodes":{"value":0,"limit":1500000},"postexpandincludesize":{"value":111495,"limit":2097152},"templateargumentsize":{"value":1401,"limit":2097152},"expansiondepth":{"value":8,"limit":40},"expensivefunctioncount":{"value":4,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":43835,"limit":5000000},"entityaccesscount":{"value":4,"limit":400},"timingprofile":["100.00% 384.835 1 -total"," 58.27% 224.229 1 Template:Reflist"," 39.09% 150.427 7 Template:Cite_journal"," 13.87% 53.363 7 Template:Navbox"," 10.72% 41.254 1 Template:Classes_of_natural_numbers"," 10.50% 40.392 3 Template:NumBlk"," 6.49% 24.962 1 Template:Cite_OEIS"," 6.46% 24.870 5 Template:Cite_web"," 4.38% 16.866 4 Template:MathWorld"," 3.68% 14.149 3 Template:Cite_book"]},"scribunto":{"limitreport-timeusage":{"value":"0.188","limit":"10.000"},"limitreport-memusage":{"value":4675661,"limit":52428800}},"cachereport":{"origin":"mw1275","timestamp":"20181202032350","ttl":1900800,"transientcontent":false}}});});{"@context":"https://schema.org","@type":"Article","name":"Lucas pseudoprime","url":"https://en.wikipedia.org/wiki/Lucas_pseudoprime","sameAs":"http://www.wikidata.org/entity/Q3343106","mainEntity":"http://www.wikidata.org/entity/Q3343106","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https://www.wikimedia.org/static/images/wmf-hor-googpub.png"}},"datePublished":"2004-10-10T19:34:33Z","dateModified":"2018-10-09T16:27:02Z"}(window.RLQ=window.RLQ||).push(function(){mw.config.set({"wgBackendResponseTime":115,"wgHostname":"mw1332"});});
-

Popular posts from this blog

Florida Star v. B. J. F.

Image
Florida Star v. B. J. F. From Wikipedia, the free encyclopedia Jump to navigation Jump to search United States Supreme Court case Florida Star v. B. J. F. Supreme Court of the United States Argued March 21, 1989 Decided June 21, 1989 Full case name The Florida Star v. B. J. F. Citations 491 U.S. 524 ( more ) 109 S. Ct. 2603; 105 L. Ed. 2d 443; 1989 U.S. LEXIS 3120; 57 U.S.L.W. 4816; 16 Media L. Rep. 1801 Prior history The Florida Star v. B.J.F., 530 So.2d 286 (1988) Supreme Court of Florida; Florida Star v. B.J.F., 499 So.2d 883 (1986) Fla. Dist. Court of Appeals Holding Florida Stat. § 794.03 is unconstitutional to the extent it makes the truthful reporting of information that was a matter of public record unlawful, as it violates the First Amendment. Court membership Chief Justice William Rehnquist Associate Justices William J. Brennan Jr.  · Byron White Thurgood Marshall  · Harry Blac...
Read more

Danny Elfman

Image
Danny Elfman From Wikipedia, the free encyclopedia Jump to navigation Jump to search Danny Elfman Elfman at the 2010 San Diego Comic-Con Born Daniel Robert Elfman ( 1953-05-29 ) May 29, 1953 (age 65) Los Angeles, California, U.S. Spouse(s) Bridget Fonda ( m.  2003) Children 1 Musical career Genres Rock [1] ska [2] new wave film music video game music Occupation(s) Composer, singer, songwriter, record producer Instruments Trombone guitar percussion vocals keyboards [3] Years active 1972–present Associated acts Oingo Boingo James Newton Howard Daniel Robert Elfman (born May 29, 1953) is an American composer, singer, songwriter, and record producer. Elfman first became known for being the lead singer and songwriter for the band Oingo Boingo from 1974 to 1995. He is well known for scoring films and television shows, particularly his frequent collabora...
Read more

Lugert, Oklahoma

Image
Unincorporated community in Oklahoma, United States Lugert, Oklahoma Unincorporated community Foundations from the town of Lugert at the bottom of Lake Altus-Lugert Lugert, Oklahoma Location within the state of Oklahoma Coordinates: 34°53′45″N 99°16′31″W  /  34.89583°N 99.27528°W  / 34.89583; -99.27528 Coordinates: 34°53′45″N 99°16′31″W  /  34.89583°N 99.27528°W  / 34.89583; -99.27528 Country United States State Oklahoma County Kiowa Time zone UTC-6 (Central (CST))  • Summer (DST) UTC-5 (CDT) GNIS feature ID 1100597 Lugert is an unincorporated community in Kiowa County, Oklahoma. [1] The town of Lugert was founded in 1901 on 80 acres (320,000 m 2 ). In the town, there was a general store that housed the Post office and sold dry goods, school supplies, groceries, harnesses, axes and much more. It was named for Frank Lugert, who had moved to the area in 1898. Lugert owned land where the town was sited and also owned the general st...
Read more