Radice primitiva di un numero primo

Radice primitiva di un numero primo

Nei blog precedenti abbiamo visto che il Teorema B dimostrava solo la primalità dell'esponente; ma lo stesso procedimento può servire, invece, a risolvere altro.

Uno dei problemi fondamentali nella ricerca della primalità di un numero primo è che se quest'ultimo è molto grande occorre affidarsi a metodi probabilistici, che comunque richiedono tempo per dare un responso.

Il numero di Wagstaff dà l'illusione di ridurre il numero primo da valutare ad 1/3; però se si trasforma il numero che si ottiene in binario (binary di PARI/GP) il risparmio è di 1 bit che è poca cosa.

E' chiaro che se esistesse un metodo tale che per poter sapere se un numero enorme è primo sia sufficiente riferirsi ad un numero molto più basso, sarebbe a dir poco eccezionale. In teoria metodi del genere esistono, ma nella pratica si scontrano con le implementazioni e i limiti hardware e software.

Abbiamo visto col Piccolo Teorema di Fermat che se è dato un numero primo p, allora a^(p-1) mod p = 1 per tutti gli a nell'intervallo (1,p-1).

Si definisce radice primitiva di p qualsiasi numero r tale che per ogni a appartenente all'intervallo (1,p-1) è a=r^k mod p con k&gt 1. Se p è dispari allora r è una radice primitiva di p se e solo se r^(p-1/q) mod p > 1 per ogni q divisore primo di r, allora p è primo.

Più esattamente è sufficiente che siano vere due condizioni:
r^(p-1/q) mod p > 1
r^(p-1) mod p = 1

Radice primitive di un numero primo ne esistono minimo una o più di una.

Ad esempio se p=13 r=2 è una radice primitiva di p=13; per cui p è primo

Infatti:
p-1 = 12
i divisori primi di p-1 sono q=2,3 (non dobbiamo prendere le potenze)

Scelgo 2 inizialmente e per ogni ottengo:
2^(12/2) mod 12 = 4 > 1
2^(12/3) mod 12 = 4 > 1

2^(12) mod 13 = 1

per cui già r=2 è buono.

Dovè il difetto di tutto questo? Supponiamo che il numero primo da verificare è un numero di Mersenne Mp=2^p-1 con p alto; allora le due condizioni diventano nel caso del numero di Mersenne di cercare un
r tale che:
r^((2^p-2)/q) mod p > 1
r^(2^p-2) mod p = 1

Ma abbiamo a che fare ora con una potenza di una potenza ... a parte il fatto che spesso è intrattabile lo stesso 2^p-2; in ogni caso si ricade nella ricerca di divisori q.

Uhmm ...