Talk:Lucas pseudoprime

Merger proposal

I'm suggesting a merge from Fibonacci pseudoprime, especially as much of the article on that page appears to be about Lucas pseudoprimes anyway. Richard Pinch (talk) 21:09, 1 August 2008 (UTC)

More Changes

Unless there are objections, I will reformat most of the equations that now display as text in the Lucas pseudoprimes section, modify the notation so it corresponds to that in the Baillie/Wagstaff paper listed in the references, and add more details based on that paper. -- MathPerson — Preceding unsigned comment added by MathPerson (talk • contribs) 00:59, 9 March 2013 (UTC)

March 26, 2013: changes have been made. — Preceding unsigned comment added by MathPerson (talk • contribs) 01:55, 27 March 2013 (UTC)

What, exactly, is a Fibonacci pseudoprime?

A Fibonacci pseudoprime is defined in the main article as a composite number n such that V_n = P (mod n).

However, Crandall and Pomerance (Prime Numbers: a Computational Perspective, definition 3.6.1, page 142), define a Fibonacci pseudoprime as a composite number n such that u_n-(D/n) = 0 (mod n) where u_k is the kth Fibonacci number. This definition seems more correct, especially since if P = 1 and Q = -1, the sequence of U's match the Fibonacci numbers. If P = 1 and Q = -1, then the V's for this P and Q are the Lucas numbers.

This article should probably be brought into compliance with the above reference. Comments? — Preceding unsigned comment added by MathPerson (talk • contribs) 01:37, 25 March 2013 (UTC)

March 26, 2013: gave the two definitions of Fibonacci pseudoprime, with references to both, and examples.

Pell pseudoprimes

(sequence A099011 in the OEIS) defines a Pell pseudoprime as an odd composite s.t. P(n) - (2|n) is divisible by n. This yields, with P=2, Q=-1:

${\text{ }}U_{n}-\left({\tfrac {2}{n}}\right)\equiv 0{\pmod {n}}$

generating the sequence 169, 385, 741, 961, 1121, 2001, ...

whereas the definition given on this wikipedia page is, eq(1) with P=2, Q=-1:

${\text{ }}U_{\delta (n)}\equiv 0{\pmod {n}},{\text{ where }}\delta (n)=n-\left({\tfrac {D}{n}}\right)=n-\left({\tfrac {8}{n}}\right)$

generating the sequence 35, 169, 385, 779, 899, 961, 1121, 1189, 2419, ...

These are not the same sequences. I can see why we would define it the latter way -- it matches the Fibonacci pseudoprimes and the "Pell cyclotomic pseudoprimes" of Rotkiewicz (2007). The latter generates about 20% more pseudoprimes than the former. DAJ NT (talk) 14:04, 1 October 2014 (UTC)

Wrong "strong" pseudoprimes?

We can set Q = −1, then $U_{n}$ and $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, ...

The example numbers appear to be wrong. I have written some Lucas sequence utilities in Haskell that can (efficiently) calculate the various $U_{k}{\pmod {n}}$ and $V_{k}{\pmod {n}}$ , currently limited to P = 1 and Q = -1 though I want to change that soon. Anyway, I implemented some of the tests on top of these, including the test for $V_{n}\equiv 1{\pmod {n}}$ (for the parameters given, this is exactly the Bruckman-Lucas criterion), the test for $U_{n}\equiv \left({\tfrac {D}{n}}\right){\pmod {n}}$, the test $U_{\delta (n)}\equiv 0{\pmod {n}}$ and a strong test as described in the article. Of these, 323 passes only the $U_{\delta (n)}$ test.

Note that for (in this case) numbers coprime with 10, any two of the "weak" tests mentioned (including another described in the Baillie-Wagstaff paper) imply the others, but 323 passes only one of the tests, so obviously this implication does not apply. Also note that if a number passes the strong test, it also passes all of the weak tests, but there are numbers that pass all weak tests yet do not pass the strong test. The pseudoprimes up to 10,000 for the tests (in the order of tests as listed above) are:

• 705, 2465, 2737, 3745, 4181, 5777, 6721 (i.e. Bruckman-Lucas PPs)
• 4181, 5777, 6479, 6721
• 323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149
• 4181, 5777

As you can see, the pairwise intersection of any two of the first three lists are equal (as they should be being that the last three tests rule out numbers not coprime with 10 except for 2 and 5), but the strong test is strictly more effective than the first three combined, e.g. also eliminating 6721 (= 11*13*47). (As a final note, the smallest composite number that passes any of these tests and also the Miller-Rabin test to base 2 is 252601. It passes all of the weaker tests, but not the strong test. In fact, I have so far not found a non-prime that passes the strong test for P=1 and Q=-1, and also the MR test to base 2, even though such a number would not necessarily disprove the PSW conjecture, and also not necessarily pass the (strong) Baillie-PSW test.) – Aragorn2 (talk) 16:53, 29 March 2019 (UTC)

Agree with the above.

Different user here, but I concur with the above findings. The number 323 should not appear in the list of strong Lucas (P=1, Q=-1) pseudoprimes.

The Jacobi symbol $\left({\tfrac {5}{323}}\right)$ is −1, so $\delta (323)=324$, and its decomposition is $81*2^{2}$. Therefore, to pass the strong test we must have either:

$U_{81}(1,-1)=0$, or $V_{81}(1,-1)=0$, or $V_{162}(1,-1)=0$ (all mod 323).

In fact, none of the above congruences are true. I get the following (all mod 323) if anyone wants to check:

$U_{81}(1,-1)=34$, $V_{81}(1,-1)=76$ and $V_{162}(1,-1)=287$

I'm pretty sure that 4181 is the smallest strong Lucas (P=1 Q=-1) pseudoprime, but would like to do some more testing to confirm this before editing. — Preceding unsigned comment added by 60.240.60.169 (talk) 01:45, 30 December 2019 (UTC)

Update: I have confirmed that the smallest strong Lucas (P=1, Q=-1) pseudoprime is indeed 4181, and have now edited the wikipedia article to reflect this. — Preceding unsigned comment added by 60.240.60.169 (talk) 05:24, 30 December 2019 (UTC)

Remove section on Bruckman-Lucas pseudoprimes?

I propose deleting the section on Bruckman-Lucas pseudoprimes. These numbers are already discussed (but not called "Bruckman...") in the section "Fibonacci pseudoprimes". The "Bruckman" section refers to a 1994 paper by Bruckman, but under "Fibonacci pseudoprimes", the exact same sequence refers to a 1990 paper by other people, so Bruckman didn't really discover these and wasn't the first to work with them.

The sequence of numbers is listed twice, and the OEIS sequence is referred to twice. There's no need for this duplication. Under "Fibonacci pseudoprimes", I suggest adding a reference to the Bruckman paper.

This section https://en.wiki.x.io/wiki/Lucas_pseudoprime#Bruckman-Lucas_pseudoprimes is referred to just once in Wikipedia: https://en.wiki.x.io/wiki/Lucas_number#Congruence_relations so if this section is deleted, then that link should be changed so it refers to https://en.wiki.x.io/wiki/Lucas_pseudoprime#Fibonacci_pseudoprimes

Discussion? MathPerson (talk) 12:26, 17 April 2019 (UTC)

There having been no objections, I deleted this section and added a mention of Bruckman pseudoprimes in the section on Fibonacci pseudoprimes. MathPerson (talk) 20:32, 30 July 2019 (UTC)