Test di Fermat

Da Wikipedia, l'enciclopedia libera.

Il test di Fermat è un test di primalità basato sul piccolo teorema di Fermat. Esso è uno dei primi test di primalità trovati e, come gli altri test usati normalmente, si propone di verificare non se un numero intero positivo è primo, ma se un numero dato non è primo. Infatti, dal teorema sappiamo che

se , tale che non valga , allora n non è primo.

Nulla si può dire, però, nel caso in cui tale proprietà sia verificata per qualche a, e perfino se è verificata da ogni a: n può comunque non essere primo. I numeri che, in base a, passano il test di Fermat sono detti pseudoprimi di Fermat, mentre quelli che lo passano per ogni a sono detti numeri di Carmichael: il più piccolo di questi è 561.

[modifica] Esempio 1

Un primo p passa il test per ogni base: ad esempio, preso p=7

2⁷ = 2¹ (per il Teorema di Eulero) ≡ 2 (mod 7),

oppure, equivalentemente, 2⁶ = 2⁰ (per Eulero) ≡ 1 (mod 7)-

3⁷ = 3¹ (per Eulero) ≡ 3 (mod 7),

4⁷ = 4¹ (per Eulero) ≡ 4 (mod 7),

5⁷ = 5¹ (per Eulero) ≡ 5 (mod 7),

6⁷ = 6¹ (per Eulero) ≡ 6 (mod 7).

[modifica] Esempio 2

Se n non è un numero primo, allora esisteranno molte basi (almeno metà) in cui il test dà esito positivo: diciamo che n è uno pseudoprimo in base a. Ad esempio, per n=91 abbiamo che 91=13*7 (cioè n non è primo). Con a=3, però, vale che:

3⁹⁰ = (3⁶)¹⁵ ≡ 1 (per Eulero) (mod 7)

3⁹⁰ = 3^{12 * 7 + 6} ≡ 3⁶ (per Eulero)≡ 27*27 ≡ 1*1 =1 (mod 13)

Quindi, 3⁹⁰ ≡ 1 (mod 91). Questo non vale, però, con a=2. Infatti, vediamo che:

2⁹⁰ = 2^{12 * 7 + 6} ≡ 2⁶ (per Eulero)≡ 2^{4 + 2} ≡ 16*4 ≡ 3*4 = -1 (mod 13).</math>

[modifica] Voci correlate

• Piccolo teorema di Fermat
• Numero primo
• Pseudoprimo
• Test di Wilson
• Test di Lucas-Lehmer
• Test di Miller-Rabin