Calcolatore della Funzione Toziente di Eulero

Benvenuti nel Calcolatore della Funzione Toziente di Eulero, uno strumento completo di teoria dei numeri che calcola φ(n) (funzione phi di Eulero) con scomposizione in fattori primi passo dopo passo, visualizzazione interattiva della griglia dei numeri coprimi e analisi approfondita. Sia che tu stia studiando l'algebra astratta, ti stia preparando per competizioni matematiche, lavori sulla crittografia RSA o esplori l'aritmetica modulare, questo calcolatore offre un calcolo professionale con ricchi contenuti educativi.

Cos'è la Funzione Toziente di Eulero?

La funzione toziente di Eulero φ(n), nota anche come funzione phi di Eulero, conta il numero di interi positivi da 1 a n che sono relativamente primi (coprimi) rispetto a n. Due numeri sono coprimi quando il loro massimo comune divisore (MCD) è uguale a 1.

Ad esempio, φ(12) = 4 perché esattamente quattro numeri — 1, 5, 7 e 11 — sono coprimi con 12 tra gli interi da 1 a 12.

La Formula del Prodotto

Il modo più efficiente per calcolare φ(n) utilizza la scomposizione in fattori primi di n. Se \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\), allora:

Ciò significa che moltiplichiamo n per \((1 - 1/p)\) per ogni fattore primo distinto p di n. Gli esponenti non contano — contano solo i numeri primi distinti.

Proprietà Chiave

Il Teorema di Eulero

Il teorema di Eulero è il risultato fondamentale che rende la funzione toziente cruciale nella crittografia:

Questo generalizza il piccolo teorema di Fermat (che è il caso speciale in cui n è primo). Costituisce il fondamento matematico della crittografia RSA.

Come usare questo calcolatore

1. Inserisci un intero positivo: Digita qualsiasi valore da 1 a 1.000.000 nel campo di input.
2. Usa gli esempi rapidi: Clicca sui pulsanti di esempio per provare valori classici come numeri primi, numeri composti o semiprimi in stile RSA.
3. Visualizza i risultati: Il calcolatore mostra φ(n), la scomposizione in fattori primi, il rapporto di coprimità e le proprietà rilevate.
4. Esplora la griglia dei coprimi: Per n ≤ 400, scopri quali numeri sono coprimi con n in una griglia visiva animata.
5. Studia il grafico dell'andamento: Osserva come varia φ(k) per k da 1 a min(n, 100).

Connessione con la Crittografia RSA

Nella crittografia RSA, la funzione toziente di Eulero svolge un ruolo centrale:

1. Scegli due grandi numeri primi p e q. Calcola n = p × q.
2. Calcola φ(n) = (p−1)(q−1).
3. Scegli un esponente pubblico e tale che mcd(e, φ(n)) = 1.
4. Calcola l'esponente privato d tale che e × d ≡ 1 (mod φ(n)).

La sicurezza di RSA si basa sulla difficoltà di calcolare φ(n) senza conoscere la scomposizione di n. Se un attaccante potesse calcolare efficientemente φ(n), potrebbe violare l'RSA.

Valori Comuni di φ(n)

Domande Frequenti

Cos'è la funzione toziente di Eulero?

La funzione toziente di Eulero φ(n), chiamata anche funzione phi di Eulero, conta il numero di interi positivi da 1 a n che sono relativamente primi (coprimi) rispetto a n. Due numeri sono coprimi quando il loro massimo comune divisore (MCD) è 1. Ad esempio, φ(12) = 4 perché solo 1, 5, 7 e 11 sono coprimi con 12.

Come si calcola la funzione toziente di Eulero?

Per calcolare φ(n): (1) Trova la scomposizione in fattori primi di n. (2) Applica la formula del prodotto: φ(n) = n × ∏(1 − 1/p) per ogni fattore primo distinto p di n. Ad esempio, φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4. Per un numero primo p, φ(p) = p−1. Per una potenza di un primo p^k, φ(p^k) = p^k − p^(k−1).

Perché la funzione toziente di Eulero è importante nella crittografia RSA?

Nella crittografia RSA, il modulo n = p × q è il prodotto di due grandi numeri primi. Il toziente φ(n) = (p−1)(q−1) viene utilizzato per calcolare la chiave privata: l'esponente di decrittazione d deve soddisfare e × d ≡ 1 (mod φ(n)), dove e è l'esponente di cifratura pubblico. Senza conoscere φ(n) — che richiede la scomposizione di n — calcolare d è computazionalmente impossibile.

Cos'è il teorema di Eulero e come si relaziona alla funzione toziente?

Il teorema di Eulero afferma che se a e n sono coprimi, allora a^φ(n) ≡ 1 (mod n). Questa è una generalizzazione del piccolo teorema di Fermat (che si applica quando n è primo). È fondamentale nell'aritmetica modulare e nella crittografia, fornendo la base matematica per la cifratura RSA e l'esponenziazione modulare efficiente.

Quali sono le proprietà chiave della funzione toziente di Eulero?

Le proprietà chiave includono: (1) φ(1) = 1. (2) Per un primo p: φ(p) = p−1. (3) Per una potenza di un primo p^k: φ(p^k) = p^(k−1)(p−1). (4) Proprietà moltiplicativa: se mcd(m,n) = 1, allora φ(m×n) = φ(m)×φ(n). (5) Somma sui divisori: Σ φ(d) = n per tutti i divisori d di n. (6) φ(n) è sempre pari per n > 2.

Cosa significa che due numeri sono coprimi?

Due interi a e b sono coprimi (chiamati anche relativamente primi) se il loro massimo comune divisore è 1, il che significa che non condividono fattori primi comuni. Ad esempio, 8 e 15 sono coprimi perché mcd(8,15) = 1, anche se nessuno dei due è un numero primo. La funzione toziente φ(n) conta esattamente quanti interi da 1 a n sono coprimi con n.

Risorse Aggiuntive

• Crittosistema RSA - Wikipedia
• Teorema di Eulero - Wikipedia