Numeri pseudoprimi e numeri di Carmichael

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).

Precedente Sicurezza informatica: Funzioni one way trapdoor Successivo Numeri primi e Piccolo Teorema di Fermat

Lascia un commento

*