Que proba é considerablemente máis eficaz na diferenciación de números primos ou compostos, a diferenza da proba de primalidade de Fermat e cuxo nome é unha aliteración? Dada a pregunta anterior, escriba un contexto que conteña a resposta. Pode ser de 1 a 20 frases. Contexto:
Un exemplo particularmente sinxelo dunha probabilidade é a proba de primalidade de Fermat, que se basea no feito (o pequeno teorema de Fermat) de que np<unk>n (mod p) para calquera n se p é un número primo. Se temos un número b que queremos probar para a primalidade, entón traballamos nb (mod b) para un valor aleatorio de n como a nosa proba. Un defecto desta proba é que hai algúns números compostos (os números de Carmichael) que satisfacen a identidade de Fermat aínda que non son primos, polo que a proba non ten forma de distinguir entre números primos e números de Carmichael. Os números de Carmichael son substancialmente máis raros que os números primos, polo que esta proba pode ser útil para fins prácticos. As extensións máis poderosas do test de primalidade de Fermat, como os test de Baillie-PSW, Miller-Rabin e Solovay-Strassen, están garantidas para fallar polo menos algunhas veces cando se aplican a un número composto.