Quale test è considerevolmente molto più efficace nel differenziare i numeri primi o compositi, a differenza del test di primalità di Fermat e il cui nome è un'allitterazione? Dato il contesto della domanda precedente, scrivi il contesto che contiene la risposta. Può essere da 1 a 20 frasi. Contesto:
Un esempio particolarmente semplice di un test probabilistico è il test di primalità di Fermat, che si basa sul fatto (il piccolo teorema di Fermat) che np <unk> n (mod p) per qualsiasi n se p è un numero primo. Se abbiamo un numero b che vogliamo testare per la primalità, allora calcoliamo nb (mod b) per un valore casuale di n come nostro test. Un difetto di questo test è che ci sono alcuni numeri compositi (i numeri di Carmichael) che soddisfano l'identità di Fermat anche se non sono primi, quindi il test non ha modo di distinguere tra numeri primi e numeri di Carmichael. I numeri di Carmichael sono sostanzialmente più rari dei numeri primi, quindi questo test può essere utile per scopi pratici. Le estensioni più potenti del test di primalità di Fermat, come i test Baillie-PSW, Miller-Rabin e Solovay-Strassen, sono garantite per fallire almeno alcune volte quando applicate a un numero composto.