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 F_n=2^{2^n}+1 è primo se e solo se

3^{\frac{F_n-1}{2}}\equiv -1\mod F_n

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 sorgente]

Per ogni Fn, si ha sicuramente

F_n\equiv 1\mod 4

e

F_n\equiv 2\mod 3

Per il criterio di Eulero, 3^\frac{F_n-1}{2} \equiv \left(\frac{3}{F_n}\right) \mod F_n, dove si è usato il simbolo di Legendre; se Fn è primo si può applicare la legge di reciprocità quadratica, e quindi

\left(\frac{3}{F_n}\right)=\left(\frac{F_n}{3}\right)=\left(\frac{2}{3}\right)=-1 .


Inversamente, se 3^{\frac{F_n-1}{2}}\equiv -1\mod F_n, la stessa congruenza deve valere per ogni fattore primo p di Fn; quindi si ha 3^{F_n-1}\equiv 1\mod p, 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