Calcolatore Radice Primitiva

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

Concetti Chiave e Formule

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

1. 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.
2. Clicca su Trova Radici Primitive: Premi il pulsante per calcolare tutte le radici primitive modulo n.
3. 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.
4. 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.
5. 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 su un generatore di un sottogruppo di ordine primo grande q, dove q divide p−1, 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 sottogruppi 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 questi sottogruppi.

FAQ

Operazioni matematiche avanzate:

• Calcolatore di Matrice di Adiacenza Nuovo
• Calcolatore di Antilogaritmo Popolare
• Calcolatore di funzione Beta
• Calcolatore del Coefficiente Binomiale
• Calcolatrice di distribuzione binomiale
• Calcolatore Bitwise
• Semplificatore di Algebra Booleana Nuovo
• Calcolatore del Teorema Centrale del Limite
• Calcolatore del Teorema Cinese del Resto
• Calcolatore di combinazione
• Calcolatore di Funzione di Errore Complementare
• Calcolatrice di Numeri Complessi
• Calcolatore di Frazioni Continue
• Calcolatore di Derangement (Sottofattoriale)
• Calcolatore del Percorso più Breve di Dijkstra
• Calcolatore di Entropia
• Calcolatore della funzione di errore
• Calcolatore della Funzione Toziente di Eulero
• Calcolatore di decadimento esponenziale
• Calcolatore della crescita esponenziale
• Calcolatore dell'Integrale Esponenziale
• Calcolatore di Esponenti (Alta Precisione) Popolare
• Calcolatore dell'Algoritmo Euclideo Esteso
• Calcolatrice del Fattoriale Popolare
• Calcolatore della Funzione Gamma
• Calcolatore del Rapporto Aureo
• Calcolatore di Colorazione di Grafi Nuovo
• Validatore di Sequenza di Gradi di Grafo
• Calcolatore Ordine Teoria dei Gruppi Nuovo
• Calcolatore del tempo di dimezzamento
• Verificatore di Cammino Hamiltoniano Nuovo
• Calcolatore Inclusione-Esclusione Nuovo
• Risolutore di Mappa di Karnaugh (K-Map) Nuovo
• Risolutore di Programmazione Lineare Nuovo
• Calcolatore Distribuzione Stazionaria Catena di Markov
• Calcolatore dell'Albero Ricoprente Minimo
• Calcolatore Esponenziazione Modulare Nuovo
• Calcolatore dell'Inverso Moltiplicativo Modulare
• Calcolatore Distribuzione Binomiale Negativa Nuovo
• Calcolatore di Flusso in Rete (Flusso Massimo) Nuovo
• Calcolatore del Tasso di Crescita Percentuale
• Calcolatore di Permutazione
• Calcolatore Permutazioni con Ripetizione Nuovo
• Calcolatore del Principio dei Cassetti
• Verificatore di Grafo Planare Nuovo
• Calcolatrice della Distribuzione di Poisson
• Calcolatrice delle Radici dei Polinomi con Passaggi Dettagliati
• Calcolatore Radice Primitiva
• Calcolatrice delle probabilità
• Calcolatrice di Distribuzione di Probabilità
• Calcolatore di Proporzioni
• Calcolatore di formula quadratica
• Calcolatore di Anelli e Campi Nuovo
• Calcolatore di Arrotondamento Popolare
• Calcolatrice Scientifica
• Calcolatore di notazioni scientifiche Popolare
• Calcolatore di Teoria degli Insiemi
• Calcolatore di Cifre Significative Popolare
• Risolutore del Problema del Matrimonio Stabile Nuovo
• Calcolatore di Numeri di Stirling
• Calcolatore di Somme di Cubi
• Calcolatore di somme di numeri interi positivi
• Calcolatore di Somme di Quadrati
• Calcolatore di Ordinamento Topologico Nuovo
• Risolutore del Commesso Viaggiatore (TSP) Nuovo
• Generatore di Tabella di Verità Popolare
• Generatore di Diagramma di Venn (3 Insiemi)