Calcolatore Funzione Di Eulero

Calcola il valore della funzione totiente di Eulero per un numero intero positivo.

Guida Completa alla Funzione di Eulero (φ(n))

Cos’è la Funzione di Eulero?

La funzione totiente di Eulero, indicata con φ(n), conta il numero di interi positivi fino a n che sono coprimi con n (ovvero il loro massimo comun divisore con n è 1). Questa funzione è fondamentale in:

• Teoria dei numeri: Studio delle proprietà dei numeri interi
• Crittografia: Algoritmi come RSA si basano su φ(n)
• Matematica discreta: Analisi degli anelli ℤ/ℤn

Proprietà Matematiche Chiave

1. Proprietà moltiplicativa: Se a e b sono coprimi, allora φ(ab) = φ(a)φ(b)
2. Formula per numeri primi: φ(p) = p-1 se p è primo
3. Formula generale: Se n = p₁^k₁ p₂^k₂ … pₘ^kₘ, allora φ(n) = n × (1-1/p₁) × (1-1/p₂) × … × (1-1/pₘ)
4. Teorema di Eulero: Se a e n sono coprimi, allora a^φ(n) ≡ 1 mod n

Applicazioni Pratiche

Campo	Applicazione	Esempio
Crittografia	Generazione chiavi RSA	φ(n) determina la dimensione dello spazio delle chiavi private
Teoria dei gruppi	Ordine del gruppo moltiplicativo (ℤ/ℤn)*	|(ℤ/ℤ10)*| = φ(10) = 4
Test di primalità	Algoritmi probabilistici	Test di Miller-Rabin usa proprietà di φ(n)
Matematica computazionale	Ottimizzazione algoritmi	Calcolo di inversi modulari

Metodi di Calcolo

Esistono diversi approcci per calcolare φ(n):

1. Metodo Diretto (Brute Force)

Il metodo più semplice ma meno efficiente:

1. Elenca tutti i numeri da 1 a n-1
2. Verifica per ciascuno se MCD(numero, n) = 1
3. Conta quanti numeri soddisfano la condizione

Complessità: O(n × log min(k,n)) per il calcolo del MCD

2. Fattorizzazione in Primi

Metodo efficiente per numeri grandi:

1. Fattorizza n in primi: n = p₁^k₁ p₂^k₂ … pₘ^kₘ
2. Applica la formula: φ(n) = n × (1-1/p₁) × (1-1/p₂) × … × (1-1/pₘ)

Esempio: φ(360) = 360 × (1-1/2) × (1-1/3) × (1-1/5) = 96

3. Proprietà Moltiplicativa

Utile quando n ha fattori coprimi:

1. Scomponi n in fattori coprimi: n = ab dove MCD(a,b)=1
2. Calcola φ(n) = φ(a) × φ(b)

Confronto tra Metodi

Metodo	Complessità	Vantaggi	Svantaggi	Caso d’uso ideale
Brute Force	O(n√n)	Semplice da implementare	Lento per n > 10,000	Dimostrazioni didattiche
Fattorizzazione	O(√n) per fattorizzare	Efficiente per n grandi	Richiede fattorizzazione	Applicazioni crittografiche
Moltiplicativo	O(k) dove k = #fattori	Ottimo per numeri composti	Richiede scomposizione nota	Calcoli teorici

Esempi Pratici

Calcoliamo φ(n) per alcuni valori:

Esempio 1: n = 9 (numero composto)

Fattorizzazione: 9 = 3²
φ(9) = 9 × (1 – 1/3) = 9 × (2/3) = 6
Numeri coprimi: {1, 2, 4, 5, 7, 8}

Esempio 2: n = 15 (prodotto di primi distinti)

Fattorizzazione: 15 = 3 × 5
φ(15) = 15 × (1 – 1/3) × (1 – 1/5) = 15 × (2/3) × (4/5) = 8
Numeri coprimi: {1, 2, 4, 7, 8, 11, 13, 14}

Esempio 3: n = 1 (caso speciale)

φ(1) = 1 per definizione, poiché MCD(1,1) = 1

Relazione con Altre Funzioni Aritmetiche

La funzione di Eulero è collegata a diverse altre funzioni in teoria dei numeri:

• Funzione di Möbius (μ(n)): Usata nella formula di inversione di Möbius per φ(n)
• Funzione divisore (d(n)): φ(n) spesso compare in formule che coinvolgono d(n)
• Funzione sigma (σ(n)): Somma dei divisori di n, correlata a φ(n) in alcune identità

Implementazione Computazionale

Per implementare un calcolatore efficiente di φ(n):

1. Usa l’algoritmo di Euclide per calcolare il MCD
2. Per n grandi, implementa la fattorizzazione con:
   • Test di primalità Miller-Rabin
   • Algoritmo rho di Pollard per fattorizzazione
3. Memorizza (cache) i risultati per numeri già calcolati
4. Per applicazioni crittografiche, usa librerie ottimizzate come GMP

Errori Comuni da Evitare

Quando si lavora con la funzione di Eulero:

• Dimenticare il caso n=1: φ(1) = 1, non 0
• Confondere coprimi con primi: φ(n) conta i coprimi, non i primi
• Errori nella fattorizzazione: Una scomposizione errata porta a φ(n) sbagliato
• Trascurare la proprietà moltiplicativa: Può semplificare calcoli complessi
• Non considerare la complessità: Il metodo brute force è inutilizzabile per n > 10⁶

Risorse Autorevoli

Per approfondire:

• Totient Function – Wolfram MathWorld (Risorsa enciclopedica completa)
• NIST FIPS 186-5 (Standard crittografici che usano φ(n) in DSA)
• MIT OpenCourseWare – Theory of Numbers (Corso universitario con approfondimenti)

Domande Frequenti

D: Perché φ(p) = p-1 per un primo p?

R: Perché tutti i numeri da 1 a p-1 sono coprimi con p (un numero primo non ha divisori propri).

D: Qual è il valore massimo di φ(n) per n ≤ 100?

R: Il massimo è φ(97) = 96, poiché 97 è il primo più grande sotto 100.

D: Come si relaziona φ(n) con la crittografia RSA?

R: In RSA, la chiave privata d è calcolata come l’inverso modulare di e modulo φ(n), dove n è il prodotto di due primi grandi.

D: Esiste una formula chiusa per φ(n)?

R: Sì, è data dalla formula del prodotto su tutti i primi distinti che dividono n: φ(n) = n × ∏(1 – 1/pᵢ) per pᵢ | n.

D: Qual è la complessità del miglior algoritmo conosciuto per calcolare φ(n)?

R: La complessità è dominata dalla fattorizzazione di n. L’algoritmo più efficiente conosciuto (General Number Field Sieve) ha complessità sub-esponenziale:

O(exp((c + o(1))(ln n)^(1/3)(ln ln n)^(2/3))) dove c ≈ 1.923