Vai al contenuto
OneKitly

Sette ha due radici primitive e otto nessuna

Pubblicato il 27/10/2026 · 3 min di lettura · Calcolatrici quotidiane

Lena Hoffmann

Lena Hoffmann — Redattrice Scienza e Istruzione presso OneKitly

Matematica · Fisica

Verificato su 2 fonti

Vedi il profilo →
In breve

Una radice primitiva modulo n è un numero le cui potenze percorrono ogni valore coprimo con n prima di tornare a uno. Modulo 7 ci riesce il 3: 3, 2, 6, 4, 5, 1 — tutti e sei i residui, in ordine mescolato, poi ritorno al principio. Il 5 fa lo stesso, e nient'altro, quindi sono due. Modulo 11 ci sono quattro generatori, e modulo 8 nessuno: le potenze di nessun numero raggiungono tutti i candidati, perché lì la struttura si spezza in due metà indipendenti anziché formare un unico ciclo. Il conteggio, quando i generatori esistono, vale φ(φ(n)) — per 7 è φ(6) = 2, e per 11 è φ(10) = 4.

Pubblicità

Modulo 7 i numeri 3 e 5 generano ciascuno ogni valore non nullo per moltiplicazioni ripetute. Modulo 8 non ci riesce nessuno, e modulo 11 ci sono quattro generatori.

I moduli che funzionano sono una lista corta

Generatori esistono solo per 1, 2, 4, una potenza qualsiasi di un primo dispari, e il doppio di tale potenza — nient'altro. Ciò esclude subito 8, 12 e 15, e spiega perché 9 funzioni dove 8 fallisce nonostante entrambi siano piccoli. La ragione è che la struttura moltiplicativa modulo tutto il resto si scompone in pezzi indipendenti, e nessun singolo elemento può generare un prodotto di cicli indipendenti. È un caso raro in cui la classificazione è completa, breve e verificabile contro il calcolatore in un minuto — buon esempio di un teorema più utile di una ricerca.

A cosa serve un generatore

Averne uno trasforma la moltiplicazione in addizione. Ogni valore non nullo si scrive come il generatore elevato a qualche potenza, quindi moltiplicare due valori corrisponde a sommare i loro esponenti — lo stesso trucco che i logaritmi giocano con i numeri ordinari, in un contesto finito. È quella corrispondenza che i protocolli di scambio di chiavi sfruttano: elevare un generatore condiviso a un esponente segreto è facile, e recuperare l'esponente dal risultato appare difficile, sicché due parti possono accordarsi su un valore che nessuna ha trasmesso. L'intera costruzione dipende dal fatto che il gruppo sia un unico ciclo, che è esattamente ciò che una radice primitiva garantisce.

Quanti
Quali moduli hanno generatori
ModuloGeneratoriQuanti
73, 52
92, 52
112, 6, 7, 84
8, 12, 15nessuno0
Calcolatore di radice primitivaTrova le radici primitive modulo n — i generatori g le cui potenze g¹, g², … percorrono tutti i numeri coprimi con n prima di ripetersi (ordine uguale a φ(n)). Le radici primitive esistono solo quando n è 1, 2, 4, pᵏ o 2pᵏ per un primo dispari p; lo strumento indica la più piccola, il numero esatto φ(φ(n)) e le elenca. Sono la spina dorsale della crittografia a logaritmo discreto e dello scambio di chiavi Diffie–Hellman.Prova lo strumento →
Pubblicità

Domande frequenti

Esiste una formula per il generatore più piccolo?
Nessuna è nota, e la ricerca si fa per tentativi. I candidati si provano in ordine e ogni prova è a buon mercato — basta verificare che il candidato elevato alla totiente divisa per ciascun fattore primo non valga uno — ma nulla permette di prevedere quale candidato riuscirà. In pratica il generatore più piccolo è quasi sempre un numero molto piccolo, due, tre o cinque, e le euristiche annunciano una crescita estremamente lenta con il modulo; quell'attesa è ben sostenuta e non dimostrata, forma ricorrente dei risultati in questo angolo della materia.
Perché il numero di generatori dipende da φ(φ(n))?
Perché una volta trovato un generatore, ogni altro è una sua potenza, e una potenza genera l'intero ciclo esattamente quando il suo esponente è coprimo con la lunghezza del ciclo. Il ciclo ha lunghezza φ(n), quindi il numero di esponenti utilizzabili vale φ(φ(n)), per lo stesso argomento di conteggio che definisce la totiente in partenza. Modulo 7 il ciclo ha lunghezza 6, gli esponenti coprimi con 6 sono 1 e 5, e i due generatori 3 e 5 sono il primo generatore elevato a quelle potenze. La doppia applicazione della stessa funzione non è casuale — è la stessa domanda posta sugli esponenti invece che sui valori.

Articoli che potrebbero interessarti

Tutte le guide →

Strumenti correlati

Fonti

Hai notato un errore in questo articolo?