Home | Perchè la crittografia | Crittografia a chiave segreta | Crittografia a chiave pubblica | Numeri primi | Aritmetica modulare

I test di primalità sono metodi che permettono di verificare se un numero intero casuale n è primo.

Alcuni metodi sono:

1) Metodo di forza bruta: dividere il numero n per gli interi che lo precedono

2) Il crivello di Eratostene

3) test di Wilson

Criticità: i metodi illustrati richiedono tempi proibitivi di calcolo.

3) Test probabilistico di Fermat: un metodo efficace per dimostrare che un intero n è probabilmente primo.
 

Esso consiste, dato un intero n ,nello scegliere un intero a, detto base, coprimo con n,in modo che se ,

         si dice che n è probabilmente primo, altrimenti n è composto.

Osservazioni:

• la probabilità che un numero composto passi il test ,su una base casuale, diminuisce all'aumentare di n.
• il punto di forza del metodo di Fermat è che il tempo, impiegato ad eseguire il test su n è polinomiale, cioè è esprimibile mediante un polinomio nel numero delle cifre di x.
• Recentemente (nel 2002) tre ricercatori indiani ,Agrawal, Saxena e Caya, hanno trovato un algoritmo che è polinomiale e deterministico per dimostrare la primalità di un numero; tale algoritmo però non è ancora utilizzato in pratica, perchè è molto più lento dei test probabilistici.

Home | Su | Test di primalità | Test di Fermat | Test di Wilson | Crivello Eratostene | Fattorizzazione