Test di primalità

Esistono dei test probabilistici per testare se è primo.
Definizione (394 Pseudo-primo)

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 (395 Primo di Carmichael)

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

 

Lemma sugli pseudoprimi[modifica | modifica wikitesto]

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 (398 applicazione del lemma)

. . 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