title: Test di Wilson
text: # Test di Wilson
  
  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
  
  Se si prende per n un numero piccolo, come n = 7, n - 1 = 6, si deve calcolare
  
      Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikipedia.org/v1/":): {\displaystyle 6! + 1 = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 + 1 = 721 = 7 \cdot 103 }
  
  e, quindi, divisibile per 7.
  
  ## Esempio 2
  
  Se prendo per n un numero molto grande, come n = $10^5$ + 1, è necessario fare $10^5$ operazioni, di cui $10^5$ - 1 prodotti di numeri molto grandi, il che richiede molto tempo e crescente difficoltà di calcolo.
  
  ## Utilizzabilità del test
  
  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.
  
  