Don't take life too seriously: it's just a temporary situation

Pseudoprimi

Teoria dei numeri 

In generale si dicono “pseudoprimi” i numeri composti che superano un esame di primalità passato da tutti i numeri primi e da relativamente pochi numeri composti.

 

L’interesse verso gli pseudoprimi è stimolato dal fatto che molti esami per stabilire se un intero è pseudoprimo sono molto più veloci dei migliori test di primalità noti. Per stabilire se un intero è primo, conviene quindi effettuare uno o più di questi esami: se anche uno solo fallisce, si stabilisce (velocemente) che è composto, mentre in caso contrario sappiamo che è molto probabilmente primo e la probabilità di errore può essere resa estremamente piccola in modo molto rapido. Se si vuole la certezza, si possono poi utilizzare i più lenti esami che danno la certezza assoluta (v. numeri primi), ma solo sui numeri che passano gli esami.

 

Normalmente le varie categorie vengono specificate, mentre il termine pseudoprimi da solo viene usato per gli pseudoprimi di Fermat, cioè per i numeri che soddisfano l’inverso del “piccolo” teorema di Fermat, pur non essendo primi.

 

Le principali categorie di pseudoprimi sono:

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.