Pseudoprimo di Fibonacci

In teoria dei numeri, uno pseudoprimo è un numero che passa alcuni test di primalità che passano anche tutti i numeri primi, ma che è composto. Uno pseudoprimo di Fibonacci è un intero composto n che soddisfa le seguenti condizioni:

  1. P > 0 e Q = +1 o −1
  2. Vn è congruente con P mod n.

In questo caso la notazione usata si riferisce alla sequenza di Lucas con parametri P, Q che produce una sequenza di numeri Un, Vn.

Uno pseudoprimo di Fibonacci forte può essere definito come segue:

  1. Un intero dispari composto n è anche un numero di Carmichael
  2. 2(pi + 1) | (n − 1) o 2(pi + 1) | (n − pi) per ogni primo pi che divide n.

Il più piccolo esempio conosciuto di uno pseudoprimo di Fibonacci forte è 443.372.888.629.441, che ha come fattori 17, 31, 41, 43, 89, 97, 167 e 331.

Bibliografia

  • 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, Lawrence. "On Even Fibonacci Pseudoprimes." In G.E. Bergum et al, eds. Applications of Fibonacci Numbers. Volume 4. Dordrecht: Kluwer, 1991. 277-288.

Collegamenti esterni

  Portale Crittografia