Fermat, test di

Fermat, test di

Fermat, test di in teoria dei numeri, è un test di non primalità, vale a dire una sorta di prova che, dato un numero intero, permette (ma non sempre) di stabilire se esso non è primo. Il test si basa sul piccolo teorema di Fermat, secondo il quale, se p è un numero primo e se a è un qualsiasi numero intero, allora vale la congruenza a^p ≡ a(modp). In modo equivalente, se un numero n soddisfa la condizione aⁿ ≢ a(modn) per qualche intero a, allora esso non è primo. Il test di Fermat consiste nel ripetere tale operazione al variare di a, finché non si determina (se esiste) un intero a che soddisfi la suddetta condizione. Se un tale numero esiste, allora n non è un numero primo; d’altra parte, se n è un numero primo, allora il procedimento non ha termine. Se però il procedimento non ha termine, non necessariamente n è un numero primo. Un numero n che supera il test di Fermat con base a (vale a dire tale che aⁿ ≡ a(modn)) è detto pseudoprimo (di Fermat) in base a; un numero non primo che sia uno pseudoprimo di Fermat in qualsiasi base è detto numero di → Carmichael.