Test di Pépin

Da Wikipedia, l'enciclopedia libera.

In matematica, il test di Pépin è un test di primalità che può essere usato per stabilire se un numero di Fermat è primo oppure composto.

Fu sviluppato dal matematico francese Théophile Pépin (1826-1904).

Secondo tale test il numero è primo se e solo se

Essendo l'esponente a sinistra una potenza di 2, l'espressione può essere valutata in modo relativamente rapido elevando ripetutamente al quadrato 3, con un algoritmo a tempo polinomiale; tuttavia, a causa della grandezza dei numeri Fn, il test può essere usato soltanto per valori non troppo grandi di n.

Dimostrazione[modifica | modifica wikitesto]

Per ogni Fn, si ha sicuramente

e

Per il criterio di Eulero, , dove si è usato il simbolo di Legendre; se Fn è primo si può applicare la legge di reciprocità quadratica, e quindi

.

Inversamente, se , la stessa congruenza deve valere per ogni fattore primo p di Fn; quindi si ha , ovvero l'ordine di 3 modulo p divide Fn-1, ed è quindi una potenza di 2. Ma tale ordine non divide (Fn-1)/2 (che è ancora una potenza di 2) e quindi deve essere precisamente Fn-1. Quindi p>Fn-1, e p deve essere precisamente Fn, ovvero quest'ultimo è primo.

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica