Dickson pseudoprimes and primality testing (Q4037495)

The polynomial \(g_n(x,c)= \sum_{i=1}^{[n/2]} \frac{n}{n-1} \binom{n-i}{ i} (c)^i x^{n-2i}\) is called the Dickson polynomial of parameter \(c\) and degree \(n\). An odd composite number \(n\) is called a strong Dickson pseudoprime of kind \(c\) if \(g_n(b,c)\equiv b\pmod n\) for all \(b\in\mathbb Z\). For \(c=0\) one has the Carmichael numbers and for \(c=-1\) the strong Fibonacci pseudoprime. An odd integer \(n\) is a strong Dickson pseudoprime of kind \(c=-1\) iff (i) \(n\) is a Carmichael number, (ii) \(2(p_i+1)\mid n-1\) or \(2(p_i+1)\mid n-p_i\) for every prime \(p_i\) dividing \(n\). Furthermore the authors show that any strong Dickson pseudoprime of kind \(c=-1\) is also of kind \(c=+1\) and vice versa. It is an open problem if there exist strong Dickson pseudoprimes for \(c\neq 0\). The authors give a suggestion how to improve a primality test by Baillie-Wagstaff [\textit{R. Baillie} and \textit{S. S. Wagstaff} jun., Math. Comput. 35, 1391--1417 (1980; Zbl 0458.10003)]. For the entire collection see [Zbl 0756.00008].