Generalizations of the Fibonacci pseudoprimes test

✍ Scribed by Rudolf Lidl; Winfried B. Müller

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 635 KB
• Volume: 92
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(91)90282-7

✦ Synopsis

Lidl, R. and W.B. Mtiller. Generalizations of the Fibonacci pseudoprimes test, Discrete Mathematics 92 (lwl) 211-220. Di Port0 and Filipponi recently described a generalization of the standard test for an odd composite integer n to be a pseudoprime (cf. [2]). Instead of evaluating powers of a given integer modulo n, they define a Fibonacci pseudoprime of the mth kind to be an odd composite integer n with the property V,(m) = m mod n. Here V,(m) are the generalized Lucas numbers, or equivalently, the Dickson polynomials g,(x; r) for r = -1 and evaluated at x = m. The Fibonacci pseudoprimes of the 1st kind are exactly the known Lucas pseudoprimes (cf. [I61 and [18]). Here we consider several generalizations. In this paper we indicate the following possibilities for generalizing the Fibonacci pseudoprimes test: In Section 1 we introduce a Dickson pseudoprimes test that is based on the Dickson polynomials g,(x; r) for arbitrary parameter r. The cases r = +I, -1 and 0 are important special cases; the case r = 0 represents the standard pseudoprimes test. Pairs of Dickson polynomials in two variables are used in Section 2 to give what appears to be an efficient test for so called Dickson pseudoprimality of odd composite integers. In Section 3 we suggest a different test involving rational functions with integral coefficients in numerator and denominator, called RCdei pseudoprimes test. *This paper was supported by the esterreichischen Fonds zur Fiirderung der wissenschaftlichen Forschung under FFWF-Project Nr. 6174.