Cosa sono e esempio di Numeri pseudoprimi e numeri di Carmichael

Cosa sono e esempio di Numeri pseudoprimi e numeri di Carmichael

Cosa sono e esempio di Numeri pseudoprimi e numeri di Carmichael

I numeri di Carmichael

Esistono numeri composti come:

561 (il prodotto di 3, 11 e 17)

1729 (il prodotto di 7, 13 e 19)

che, pur rispettando il Piccolo Teorema di Fermat, si comportano come se fossero numeri primi ma non lo sono. Tali numeri sono detti numeri di Carmichael.

Infatti tali numeri composti, relativamente al piccolo teorema di Fermat, si comportano come se fossero primi, ma la condizione espressa dal teorema non vale per tutti i valori di b appartenenti all’intervallo [1,p-1].

Esempio numeri di Carmichael

Consideriamo il numero composto 341 (il prodotto di 11 e 31), è infatti:

1341(mod 341)=1

2341(mod 341)=2

3341(mod 341)=168

4341(mod 341)=4

5341(mod 341)=335

6341(mod 341)=336

7341(mod 341)=51

8341(mod 341)=8

9341(mod 341)=262

…………………….

Effettuando i calcoli per tutte le basi b (da 1 a 340), diremo che 341 è uno pseudoprimo solo rispetto a 120 basi su 340. 

Esempio 2 numeri di Carmichael

Il numero composto 91 (il prodotto di 7 e 13), è uno pseudoprimo rispetto a 48 basi su 90.

Il numero composto 15 (il prodotto di 3 e 5), è uno pseudoprimo rispetto a 8 basi su 14.

OSSERVAZIONE

Fortunatamente, nei confronti dei numeri primi, i numeri di Carmichael, numeri pseudoprimi per ogni base, sono molto rari. Non è così, invece, per i numeri pseudoprimi per alcune basi (come i numeri di cui sopra: 341, 91 e 15).

 

Pubblicato da Vito Lavecchia

Lavecchia Vito Ingegnere Informatico (Politecnico di Bari) Email: [email protected] Sito Web: https://vitolavecchia.altervista.org

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *