Calcolatore Radice Primitiva

Trova tutte le radici primitive di un dato modulo n — generatori del gruppo moltiplicativo (Z/nZ)*. Inserisci qualsiasi numero intero positivo per ottenere le radici primitive, la funzione totiente di Eulero, la visualizzazione del gruppo ciclico e una verifica passo-passo con tabelle delle potenze.

Embed Calcolatore Radice Primitiva Widget

Calcolatore Radice Primitiva

Il Calcolatore Radice Primitiva trova tutte le radici primitive di un dato modulo n — numeri interi g le cui potenze \(g^1, g^2, \ldots, g^{\varphi(n)}\) generano ogni elemento del gruppo moltiplicativo \((\mathbb{Z}/n\mathbb{Z})^*\). Inserisci qualsiasi numero intero positivo per vedere istantaneamente tutte le radici primitive, il totiente di Eulero \(\varphi(n)\), una visualizzazione interattiva del gruppo ciclico, una tabella delle potenze e una verifica passo-passo della radice primitiva più piccola.

Applicazioni delle Radici Primitive

🔐

Diffie-Hellman

Il protocollo di scambio chiavi utilizza radici primitive come generatori

🔏

Crittografia ElGamal

Criptosistema a chiave pubblica basato sui logaritmi discreti

✍

Firme Digitali

Le firme DSA e Schnorr si basano sui generatori di gruppi ciclici

🎲

Numeri Pseudocasuali

I generatori congruenziali lineari utilizzano le proprietà delle radici primitive

📡

Codici Correttori

I codici Reed-Solomon e BCH utilizzano generatori di campi finiti

🧮

Teoria dei Numeri

Calcolo degli indici, residui quadratici e problemi del logaritmo discreto

Concetti Chiave e Formule

Concetto	Formula / Definizione	Descrizione
Radice Primitiva	\(\text{ord}_n(g) = \varphi(n)\)	Un intero g il cui ordine mod n è uguale al totiente di Eulero
Totiente di Eulero	\(\varphi(n) = n \prod_{p\|n}\left(1 - \frac{1}{p}\right)\)	Conteggio degli interi in [1, n] coprimi con n
Criterio di Esistenza	\(n \in \{1, 2, 4, p^k, 2p^k\}\)	Le radici primitive esistono solo per queste forme (p primo dispari)
Numero di Radici	\(\varphi(\varphi(n))\)	Conteggio delle radici primitive quando esistono
Test della Radice Primitiva	\(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\) per tutti i primi \(p \| \varphi(n)\)	Condizione sufficiente: controllare solo per i fattori primi di φ(n)
Generazione di Tutte le Radici	\(g^k \bmod n\) dove \(\gcd(k, \varphi(n)) = 1\)	Una volta trovata una radice g, seguono tutte le altre

Comprendere le Radici Primitive

Una radice primitiva modulo n è un numero intero g tale che \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) è uguale all'insieme di tutti i numeri interi da 1 a n−1 che sono coprimi con n. In termini di teoria dei gruppi, g è un generatore del gruppo moltiplicativo ciclico \((\mathbb{Z}/n\mathbb{Z})^*\). Ad esempio, 3 è una radice primitiva mod 7 perché le potenze 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) producono ogni elemento di {1, 2, 3, 4, 5, 6}.

Quando Esistono le Radici Primitive?

Un risultato classico nella teoria dei numeri (dimostrato da Gauss) afferma che le radici primitive modulo n esistono se e solo se n è uno tra: 1, 2, 4, p^k o 2p^k, dove p è un numero primo dispari e k ≥ 1. Per altri valori di n, il gruppo \((\mathbb{Z}/n\mathbb{Z})^*\) non è ciclico — si decompone come un prodotto diretto di gruppi ciclici per il Teorema Cinese dei Resti — quindi nessun singolo elemento può generare l'intero gruppo. Ad esempio, \((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\) non ha radici primitive.

Come Trovare Efficientemente le Radici Primitive

L'algoritmo standard funziona in due fasi. Fase 1: trovare la radice primitiva più piccola per tentativi. Per ogni candidato g a partire da 2, calcola \(g^{\varphi(n)/p} \bmod n\) per ogni fattore primo p di \(\varphi(n)\). Se nessuno di questi è uguale a 1, allora g è una radice primitiva. In pratica, la radice primitiva più piccola è tipicamente piccola — si ipotizza sia \(O(n^\epsilon)\) per ogni \(\epsilon > 0\). Fase 2: una volta nota una radice primitiva g, tutte le altre radici primitive sono \(g^k \bmod n\) dove \(\gcd(k, \varphi(n)) = 1\), dando esattamente \(\varphi(\varphi(n))\) radici primitive in totale.

Come usare il Calcolatore Radice Primitiva

Inserisci il modulo n: Digita un numero intero positivo nel campo di input, oppure clicca su uno dei pulsanti di esempio rapido per compilare automaticamente un valore.
Clicca su Trova Radici Primitive: Premi il pulsante per calcolare tutte le radici primitive modulo n.
Esamina i risultati: Visualizza il conteggio, l'elenco completo delle radici primitive, il totiente di Eulero, l'ordine del gruppo e se le radici primitive esistono per il tuo n.
Esplora la visualizzazione: Per n ≤ 100, la ruota interattiva del gruppo ciclico mostra come ogni radice primitiva genera l'intero gruppo attraverso le sue potenze. Clicca su qualsiasi chip della radice per vedere il suo ciclo animato sulla ruota.
Studia la tabella delle potenze: La griglia mostra g^k mod n per k = 1, 2, …, φ(n), con le radici primitive e l'elemento identità evidenziati in colori distinti.

Radici Primitive in Crittografia

Le radici primitive giocano un ruolo centrale nella crittografia moderna. Nello scambio di chiavi Diffie-Hellman, due parti concordano su un grande numero primo p e una radice primitiva g mod p, quindi scambiano le chiavi pubbliche g^a mod p e g^b mod p. Il segreto condiviso g^ab mod p è computazionalmente impossibile da determinare per un intercettatore, perché si ritiene che il calcolo dei logaritmi discreti in grandi gruppi ciclici sia difficile. Allo stesso modo, la crittografia ElGamal e il Digital Signature Algorithm (DSA) si basano entrambi sulla difficoltà del problema del logaritmo discreto in gruppi generati da radici primitive.

FAQ

Cos'è una radice primitiva modulo n?

Una radice primitiva modulo n è un numero intero g tale che le potenze g¹, g², …, g^φ(n) modulo n producono ogni numero intero coprimo con n esattamente una volta. Equivalentemente, g ha un ordine moltiplicativo uguale a φ(n), il che significa che g genera l'intero gruppo moltiplicativo (Z/nZ)*.

Per quali valori di n esistono le radici primitive?

Le radici primitive esistono se e solo se n è 1, 2, 4, p^k o 2p^k, dove p è un numero primo dispari e k è un numero intero positivo. Ad esempio, n = 7 (primo), n = 9 (3²) e n = 14 (2 × 7) hanno tutti radici primitive, ma n = 8, n = 12 e n = 15 no.

Quante radici primitive ha n?

Se n ha radici primitive, allora il numero di radici primitive modulo n è uguale a φ(φ(n)), dove φ è la funzione totiente di Eulero. Ad esempio, n = 7 ha φ(φ(7)) = φ(6) = 2 radici primitive, che sono 3 e 5.

Come si trovano le radici primitive?

Per trovare le radici primitive di n: prima calcola φ(n) e fattorizzalo. Quindi, per ogni candidato g coprimo con n, controlla se g^(φ(n)/p) non è congruente a 1 mod n per ogni fattore primo p di φ(n). Se tutti i controlli passano, g è una radice primitiva. Tutte le altre radici possono essere trovate come g^k mod n dove mcd(k, φ(n)) = 1.

Perché le radici primitive sono importanti nella crittografia?

Le radici primitive sono fondamentali per lo scambio di chiavi Diffie-Hellman, la crittografia ElGamal e gli algoritmi di firma digitale. Garantiscono che il problema del logaritmo discreto sia difficile, il che è la base della sicurezza per questi protocolli crittografici. Una radice primitiva genera tutti gli elementi del gruppo, massimizzando lo spazio di ricerca per gli attaccanti.

Cita questo contenuto, pagina o strumento come:

"Calcolatore Radice Primitiva" su https://MiniWebtool.com/it/calcolatore-radice-primitiva/ di MiniWebtool, https://MiniWebtool.com/

dal team miniwebtool. Aggiornato: 2026-04-16

Puoi anche provare il nostro Risolutore di Matematica AI GPT per risolvere i tuoi problemi matematici attraverso domande e risposte in linguaggio naturale.

Altri strumenti correlati:

Calcolatore del Teorema Cinese del Resto

Calcolatore della Funzione Toziente di Eulero

Calcolatore Esponenziazione ModulareNuovo

Calcolatore dell'Inverso Moltiplicativo Modulare

Calcolatore di Fattorizzazione Prima

Calcolatore Radice Primitiva

Calcolatore Radice Primitiva

Applicazioni delle Radici Primitive

Concetti Chiave e Formule

Comprendere le Radici Primitive

Quando Esistono le Radici Primitive?

Come Trovare Efficientemente le Radici Primitive

Come usare il Calcolatore Radice Primitiva

Radici Primitive in Crittografia

FAQ

Altri strumenti correlati:

Operazioni matematiche avanzate:

Strumenti in primo piano: