Test di Wilson

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

Il test di Wilson per la primalità di un numero intero positivo n deriva direttamente dal teorema di Wilson. Il test si applica in questo modo: dato un numero intero positivo n (possibilmente dispari, se n ≠ 2, altrimenti è divisibile per 2), si calcola (n - 1)! + 1 e si verifica se tale numero sia divisibile per n oppure non lo sia. A quel punto, se (n - 1)! + 1 è divisibile per n allora n è primo, in caso contrario n non è primo.

Si nota immediatamente che questo test dà grandissimi problemi computazionali, come si nota da questi due esempi.

Se si prende per n un numero piccolo, come n = 7, n - 1 = 6, si deve calcolare

${\displaystyle 6!+1=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6+1=721=7\cdot 103}$

e, quindi, divisibile per 7.

Se prendo per n un numero molto grande, come n = 10⁵ + 1, è necessario fare 10⁵ operazioni, di cui 10⁵ - 1 prodotti di numeri molto grandi, il che richiede molto tempo e crescente difficoltà di calcolo.

Si capisce quindi che questo test è in pratica inutilizzabile per numeri grandi, e che si basa su un algoritmo esponenziale (la quantità di calcoli è basata su (n - 1)! il cui calcolo è esponenziale). Più utili, per trattare numeri grandi, sono i test di Lucas - Lehmer e test di Miller - Rabin.

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

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