Quina prova és considerablement més eficaç per diferenciar nombres primers o compostos, a diferència de la prova de primalitat de Fermat i el nom és una aliteració? Tenint en compte la pregunta anterior, escriu un context que conté la resposta. Pot ser de 1 a 20 frases. Context:
Un exemple particularment simple d'una prova probabilística és la prova de primalitat de Fermat, que es basa en el fet (el petit teorema de Fermat) que np <unk> n (mod p) per a qualsevol n si p és un nombre primer. Si tenim un nombre b que volem provar per a la primalitat, llavors calculem nb (mod b) per a un valor aleatori de n com a prova. Un defecte d'aquesta prova és que hi ha alguns nombres compostos (els nombres de Carmichael) que satisfan la identitat de Fermat encara que no siguin primers, de manera que la prova no té manera de distingir entre nombres primers i nombres de Carmichael. No obstant això, els nombres de Carmichael són substancialment més rars que els nombres primers, de manera que aquesta prova pot ser útil per a propòsits pràctics. Les extensions més potents de la prova de primalitat de Fermat, com les proves de Baillie-PSW, Miller-Rabin i Solovay-Strassen, estan garantides per fallar almenys part del temps quan s'apliquen a un nombre compost.