All’interno di questo articolo discuteremo brevemente il tema dei test di primalità, un insieme di test che permettono di stabilire con certezza, o con un certo margine di probabilità, la primalità del numero sotto esame. In matematica si dice primo un numero naturale maggiore di 1 (1 non è un numero primo) che ammette come divisori solo 1 e sé stesso. I numeri primi sono largamente utilizzati in statistica e in crittografia come base per diversi critto-sistemi.

I primi numeri primi sono: 2, 3, 5, 7, 11, 13, 17, \dots

Un numero non primo è detto composto, se n è un numero composto allora esso avrà sicuramente un fattore compreso tra 2 e n .

Test basilare di primalità

Consideriamo un numero n grande da controllare, se esistono due numeri x e y tali che:
x^2 = y^2 \pmod{n}
x^2 \neq y^2 \pmod{n}

Allora n è un numero composto e uno dei suoi due fattori è:
a = \text{MCD}(n, x-y)

È possibile calcolare il secondo dei due fattori mediante la formula:
b = n \cdot a

Quello appena presentato è un test di tipo probabilistico, esso non garantisce la primalità del numero, tuttavia la afferma con un certo grado di probabilità.

Test di Fermat

Consideriamo un numero n grande da controllare, scegliamo un numero a casuale tale che: 1 < a < n . Il numero n è composto se vale la relazione: a^{n-1} \neq 1 \pmod{n} per qualche valore di a . Il test di Fermat è un testo probabilistico, la probabilità che n sia realmente primo aumenta all'aumentare del numero di tentativi effettuati.

Test di Miller-Rabin

Il test di Miller-Rabin è un po’ più laborioso dei precedenti ma può essere sintetizzato in questo modo:

  1. Si sceglie un numero b_1 casuale tale che: 0 < b_1 < n ;
  2. Se MCD(n, b1)=1 allora n è probabilmente primo, in caso contrario è composto;
  3. Si calcola il valore b_1^2 \pmod{n} . Se questo valore è uguale a +1 o -1 allora il numero è probabilmente primo, in caso contrario è composto;
  4. Si calcola il valore b_1^4 \pmod{n} . Se questo valore è uguale a -1 allora il numero è probabilmente primo, in caso contrario è composto;
  5. Provo con altre potenze di 2, b_1^t \pmod{n} . Se il valore risultante sarà uguale a -1 allora il numero sarà probabilmente primo.

Il test di Miller-Rabin è un testo probabilistico, la probabilità di avere n realmente primo sale all’aumentare del numero di tentativi effettuati. L’errore di questo test è del 25%.

Considerazioni finali

Un numero è pseudo-primo se è composto e passa il test di Fermat. Un numero è pseudo primo forte se è composto e passa sia il test di Fermat che il test di Miller-Rabin.