Test di Wilson

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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.

Esempio 1[modifica | modifica wikitesto]

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

e, quindi, divisibile per 7.

Esempio 2[modifica | modifica wikitesto]

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

Utilizzabilità del test[modifica | modifica wikitesto]

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.

Voci correlate[modifica | modifica wikitesto]

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