Sia un intero, e sia un intero dispari positivo, non primo, e tali che , e . Scriviamo , con dispari. Il numero si dice uno pseudoprimo forte in base se vale una delle seguenti condizioni:
Sia un numero intero positivo dispari e un intero positivo tale che . Se , allora è uno pseudoprimo forte in base se e solo se è uno pseudoprimo di Eulero-Jacobi in base .
Infatti, se , segue facilmente che . Quindi, è uno pseudoprimo forte in base se e solo se:
Viceversa, sia uno pseudoprimo forte in base . Poiché , si ha che:
e, dunque,
Vi sono altre due proprietà, che elenchiamo senza dimostrazione.
Sia un numero intero positivo dispari e un numero intero positivo tale che . Se è uno pseudoprimo forte in base , allora è uno pseudoprimo di Eulero-Jacobi in base .
Sia un numero intero positivo dispari e non primo. I numeri positivi tali che , e tali che sia uno pseudoprimo forte in base sono non più di un quarto di tutti i numeri positivi tali che .
Gli pseudoprimi forti hanno un importante ruolo nella crittografia moderna, poiché sono spesso utilizzati in algoritmi che sfruttano test di primalità probabilistici, come RSA, che usa l'algoritmo del test di Miller - Rabin per trovare dei numeri primi molto grandi.