Test di primalità

Esistono dei test probabilistici per testare se è primo.


Definizione

si dice uno pseudo-primo rispetto alla base se , dove , e se .

 



Passi del test di primalità:

  1. Scegli con e calcola .
  2. Se è diverso da 1, non è primo (costo di operazioni).
  3. Se , calcolo .
  4. Se , restituisce " non primo".
  5. Se , restituisci " è pseudoprimo rispetto alla base ".


Questo test funziona perché, se fosse primo, si avrebbe . Per Eulero-Fermat, con coprimi, si avrebbe , quindi . Quindi se questo non avviene il numero non è primo. Tuttavia se si ha , non è detto che il numero sia primo.


Ci sono numeri che risultano pseudoprimi per qualsiasi base anche se non sono numeri primi.


Definizione

Un numero si dice primo di Carmichael se è pseudoprimo rispetto a ogni con .

 

Lemma sugli pseudoprimi

Lemma (396)

Sia un numero naturale, allora

  1. se è pseudoprimo rispetto alle basi , allora è pseudoprimo rispetto alla base
  2. se esiste una base per cui non è uno pseudoprimo, allora ce ne sono almeno con tale proprietà.
 
Dimostrazione

Dimostro il punto 2 del lemma: Siano tutte le basi per cui è pseudoprimo, e sia una base per cui non è pseudoprimo. Allora

Considero i numeri , allora non è pseudoprimo per nessuno di queste basi, che sono almeno . Questo mostra che il numero di basi per cui non è pseudoprimo è almeno quanto il numero di basi per cui è pseudoprimo. Sia il numero di basi per cui non è pseudoprimo. Allora , inoltre , perché è il numero totale di elementi coprimi con . Unendo le due equazioni e , si ha , cioè .

 


Lemma (397)
  1. Se è primo di Carmichael, allora è senza quadrati (come i numeri utilizzati nel protocollo RSA).
  2. è primo di Carmichael se e solo se per ogni divisore primo di ;
  3. se è primo di Carmichael, allora è divisibile per almeno tre primi.
 


Esempio

. . I divisori primi di sono , e si ha che dividono , cioè per ogni divisore , e quindi è il più piccolo primo di Carmichael. Senza conoscere la fattorizzazione di , basta estrarne la radice cubica e verificare se ha divisori.

 
 PrecedenteSuccessivo