Calcolatore di Radice Primitiva

Benvenuti nel Calcolatore di Radice Primitiva, un potente strumento online gratuito che trova tutte le radici primitive modulo qualsiasi numero intero positivo n. Questo calcolatore fornisce una verifica passo-passo, tabelle di potenza e una visualizzazione animata del gruppo ciclico per aiutarti a capire come le radici primitive generano gruppi moltiplicativi. Che tu stia studiando teoria dei numeri, preparandoti per esami di crittografia o lavorando con l'aritmetica modulare nella programmazione competitiva, questo strumento fornisce risultati istantanei e accurati con approfondimenti didattici.

Cos'è una radice primitiva?

Una radice primitiva modulo n è un intero g le cui potenze generano tutti gli interi che sono coprimi con n. Formalmente, g è una radice primitiva mod n se l'ordine moltiplicativo di g modulo n è uguale al totiente di Eulero \(\varphi(n)\). Ciò significa che l'insieme

contiene esattamente tutti i \(\varphi(n)\) interi da 1 a n-1 che sono coprimi con n. Una radice primitiva è essenzialmente un generatore del gruppo ciclico \((\mathbb{Z}/n\mathbb{Z})^*\).

Esempio Rapido

Consideriamo n = 7. Poiché 7 è primo, \(\varphi(7) = 6\). Verifichiamo se g = 3 è una radice primitiva:

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

Le potenze producono {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}, ovvero tutti gli interi coprimi con 7. Quindi 3 è una radice primitiva modulo 7.

Quando esistono le radici primitive?

Le radici primitive modulo n esistono se e solo se n è una di queste forme:

• n = 1, 2, o 4
• n = p^k dove p è un numero primo dispari e k ≥ 1
• n = 2p^k dove p è un numero primo dispari e k ≥ 1

Ad esempio, le radici primitive esistono per 7, 9, 11, 13, 14, 18, 23, 25, 27, 46, ma non per 8, 12, 15, 16, 20, 21, 24.

Come trovare le radici primitive

1. Inserisci il modulo: Digita un numero intero positivo n (da 2 a 100.000) nel campo di input.
2. Calcola: Fai clic su "Trova Radici Primitive" o premi Invio.
3. Visualizza tutte le radici: Vedi l'elenco completo delle radici primitive, insieme al totiente di Eulero e alle statistiche.
4. Studia la tabella delle potenze: Esamina come la radice primitiva più piccola genera tutti i residui coprimi.
5. Visualizza il gruppo ciclico: Per i piccoli moduli, osserva la ruota animata che mostra la struttura ciclica.

Quante radici primitive ha n?

Se esistono radici primitive modulo n, il numero è pari a:

Ad esempio, per n = 13: \(\varphi(13) = 12\) e \(\varphi(12) = 4\), quindi ci sono esattamente 4 radici primitive modulo 13 (che sono 2, 6, 7, 11).

L'algoritmo di verifica

Per verificare se g è una radice primitiva modulo n in modo efficiente:

1. Calcola \(\varphi(n)\) usando la fattorizzazione in primi di n
2. Trova tutti i distinti fattori primi \(p_1, p_2, \ldots, p_k\) di \(\varphi(n)\)
3. Per ogni fattore primo \(p_i\), controlla che: \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)
4. Se TUTTI i controlli passano, allora g è una radice primitiva

Questo metodo è molto più veloce del calcolo di tutte le potenze di g, poiché dobbiamo testare solo \(k\) esponenziazioni invece di \(\varphi(n)\) di esse.

Radici primitive nella crittografia

Scambio di chiavi Diffie-Hellman

Il protocollo Diffie-Hellman utilizza un numero primo grande p e una radice primitiva g modulo p. Alice sceglie un segreto a, invia \(g^a \bmod p\). Bob sceglie un segreto b, invia \(g^b \bmod p\). Entrambi calcolano il segreto condiviso \(g^{ab} \bmod p\). La sicurezza si basa sul fatto che il problema del logaritmo discreto sia computazionalmente difficile.

Crittografia ElGamal

Anche ElGamal utilizza una radice primitiva come generatore. La chiave pubblica è \((p, g, g^x \bmod p)\) dove x è privato. Il fatto che g generi tutti gli elementi assicura che ogni messaggio possa essere crittografato.

Firme digitali

Il DSA (Digital Signature Algorithm) e schemi correlati utilizzano radici primitive in sottogruppi di \((\mathbb{Z}/p\mathbb{Z})^*\) per creare e verificare le firme digitali.

Tabella di riferimento: radici primitive più piccole

Domande frequenti

Cos'è una radice primitiva modulo n?

Una radice primitiva modulo n è un intero g tale che le potenze \(g^1, g^2, \ldots, g^{\varphi(n)}\) producono tutti gli interi coprimi con n quando presi modulo n. In altre parole, g genera l'intero gruppo moltiplicativo \((\mathbb{Z}/n\mathbb{Z})^*\). L'ordine moltiplicativo di g modulo n è uguale al totiente di Eulero \(\varphi(n)\).

Per quali valori di n esistono radici primitive?

Le radici primitive esistono modulo n se e solo se n è 1, 2, 4, p^k, o 2p^k, dove p è un numero primo dispari e k ≥ 1. Ad esempio, le radici primitive esistono per n = 7 (primo), n = 9 (3²), n = 14 (2×7), ma NON per n = 8, 12, 15 o 16.

Quante radici primitive ha n?

Se esistono radici primitive modulo n, il numero di radici primitive è uguale a \(\varphi(\varphi(n))\), dove \(\varphi\) è la funzione totiente di Eulero. Ad esempio, per n = 13 (primo), \(\varphi(13) = 12\) e \(\varphi(12) = 4\), quindi ci sono esattamente 4 radici primitive modulo 13.

Perché le radici primitive sono importanti nella crittografia?

Le radici primitive sono fondamentali per il protocollo di scambio di chiavi Diffie-Hellman e il sistema di crittografia ElGamal. In questi protocolli crittografici, una radice primitiva g modulo un numero primo grande p viene utilizzata come generatore. La sicurezza si basa sulla difficoltà del problema del logaritmo discreto: dato \(g^x \bmod p\), è computazionalmente difficile trovare x.

Come si verifica che g è una radice primitiva modulo n?

Per verificare che g è una radice primitiva mod n: (1) Calcola \(\varphi(n)\). (2) Trova tutti i fattori primi \(p_1, p_2, \ldots, p_k\) di \(\varphi(n)\). (3) Verifica che \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\) per ogni fattore primo \(p_i\). Se tutti i controlli passano, g è una radice primitiva. Questo è molto più veloce del calcolo di tutte le potenze di g.

Strumenti correlati