In number theory, a pseudoprime is a number that passes some test that all primes pass, but is actually composite. A Fibonacci pseudoprime is a composite integer n that satisfies the following conditions:

1. P > 0 and Q = +1 or −1
2. V_n is congruent to P mod n.

Here the notation refers to the Lucas sequence with parameters P, Q producing a series of numbers U_n, V_n.

It is conjectured that there are no even Fibonacci pseudoprimes (see Somer).

A strong Fibonacci pseudoprime may defined as follows (see Müller and Oswald):

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

References

• Müller, Winfired 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. 459-464.
• Somer, Larence. "On Even Fibonacci Pseudoprimes." In G.E. Bergum et al, eds. Applications of Fibonacci Numbers. Volume 4. Dordrecht: Kluwer, 1991. 277-288.

External links

• Anderson, Peter G. (http://www.cs.rit.edu/~pga/homepage.html) Fibonacci Pseudoprimes, their factors, and their entry points. (http://www.cs.rit.edu/usr/local/pub/pga/fpp_and_entry_pts)
• Anderson, Peter G. (http://www.cs.rit.edu/~pga/homepage.html) Fibonacci Pseudoprimes under 2,217,967,487 and their factors. (http://www.cs.rit.edu/usr/local/pub/pga/fibonacci_pp)
• Dénes, Tamás. On the connections between RSA cryptosystem and the Fibonacci numbers. (http://www.titoktan.hu/_raktar/_e_vilagi_gondolatok/Puma-FIBO_RSA.htm)
• MathWorld: Fibonacci Pseudoprime (http://mathworld.wolfram.com/FibonacciPseudoprime.html)