Calcolatore di Anelli e Campi

Calcolatore di Anelli e Campi

Il Calcolatore di Anelli e Campi esegue l'aritmetica esatta all'interno delle due più importanti famiglie di strutture algebriche finite: gli anelli modulari Z_n e i campi finiti di Galois GF(p^k). Gestisce addizione, sottrazione, moltiplicazione, divisione, potenze, inversi moltiplicativi e ordine degli elementi, arricchendo ogni risultato con un'analisi strutturale — unità, divisori dello zero, nilpotenti, idempotenti, radici primitive e tabelle di Cayley complete codificate a colori.

Z_n — L'anello modulare

Per un intero positivo n, l'anello Z_n = {0, 1, 2, …, n − 1} supporta l'addizione e la moltiplicazione ridotte modulo n. Un elemento a è un'unità di Z_n (cioè ha un inverso moltiplicativo) se e solo se mcd(a, n) = 1, pertanto il gruppo moltiplicativo Z_n* ha ordine φ(n), la funzione totiente di Eulero.

Quando n è composto, gli elementi a con mcd(a, n) > 1 sono divisori dello zero: esiste un b ≠ 0 tale che a · b ≡ 0 (mod n). Il calcolatore classifica automaticamente ogni elemento nel suo ruolo strutturale.

Trovare gli inversi — Algoritmo di Euclide esteso

Se mcd(a, n) = 1 l'algoritmo di Euclide esteso produce interi x, y tali che a · x + n · y = 1, da cui a⁻¹ ≡ x (mod n). Lo strumento mostra l'identità di Bézout risultante ogni volta che viene richiesto un inverso.

Ordine moltiplicativo

Per un'unità a, l'ordine moltiplicativo ord(a) è il minimo k ≥ 1 tale che a^k ≡ 1 (mod n). Per il teorema di Lagrange ord(a) divide φ(n). Un elemento con ord(a) = φ(n) è chiamato radice primitiva e genera l'intero gruppo delle unità. Una radice primitiva esiste precisamente quando n è uno tra 1, 2, 4, p^k, o 2p^k per un primo dispari p.

GF(p^k) — Campi finiti (di Galois)

Per ogni primo p e intero positivo k esiste un unico campo (a meno di isomorfismi) con p^k elementi: il campo di Galois GF(p^k) = 𝔽_p^k. I suoi elementi sono rappresentati come polinomi di grado < k con coefficienti in GF(p) = Z_p, e l'aritmetica viene eseguita modulo un polinomio irriducibile f(x) di grado k.

Il calcolatore suggerisce un polinomio irriducibile standard per le coppie comuni (p, k), ad esempio x² + x + 1 per GF(4), x³ + x + 1 per GF(8), x⁴ + x + 1 per GF(16) e x² + 1 per GF(9). È possibile sovrascriverlo con il proprio; lo strumento verifica l'irriducibilità tramite un test gcd in stile Rabin.

Perché f(x) deve essere irriducibile?

Se f(x) fosse fattorizzabile come g(x)·h(x) con deg g, deg h ≥ 1, allora l'immagine di g(x) e h(x) nel quoziente sarebbe costituita da divisori dello zero non nulli — il quoziente sarebbe solo un anello, non un campo. L'irriducibilità è esattamente la condizione affinché GF(p)[x] / ⟨f(x)⟩ sia un campo.

Aritmetica polinomiale e inversi

L'addizione avviene coefficiente per coefficiente mod p. La moltiplicazione è l'ordinaria moltiplicazione polinomiale seguita dalla riduzione: dato a(x)·b(x), si divide per f(x) e si tiene il resto r(x), con deg r < k. Gli inversi moltiplicativi derivano dall'algoritmo di Euclide esteso sull'anello dei polinomi GF(p)[x]: trovare u(x) e v(x) tali che u(x)·a(x) + v(x)·f(x) = 1.

Anelli vs Campi a colpo d'occhio

Come usare il calcolatore

1. Scegli una struttura — Z_n per interi modulari, o GF(p^k) per un campo di estensione. Il modulo si riorganizzerà per mostrare solo i campi rilevanti.
2. Inserisci i parametri — il modulo n, o il primo p e il grado k. Per GF(p^k) puoi lasciare vuoto il polinomio irriducibile e il calcolatore ne inserirà uno standard.
3. Scegli un'operazione — le sette opzioni coprono tutte le attività comuni: somma, sottrazione, moltiplicazione, divisione, elevamento a potenza, calcolo dell'inverso o dell'ordine moltiplicativo.
4. Inserisci gli operandi — interi per Z_n, o polinomi come x^2 + x + 1 per GF(p^k). Funziona anche la forma a lista di coefficienti (1,1,1).
5. Clicca su Calcola. Vedrai il risultato insieme al procedimento passo-passo, alla classificazione di ogni elemento e alle tabelle di Cayley ogni volta che la struttura è sufficientemente piccola da essere visualizzata.

Esempio svolto — GF(8) = GF(2³)

Sia f(x) = x³ + x + 1 (irriducibile su GF(2)). Moltiplica a(x) = x + 1 per b(x) = x²:

Il gruppo moltiplicativo GF(8)* è ciclico di ordine 7, e l'elemento x è un elemento primitivo perché x^k attraversa ogni elemento non nullo per k = 1, 2, …, 7.

Perché questo è importante

• Crittografia — AES utilizza l'aritmetica in GF(2⁸) con f(x) = x⁸ + x⁴ + x³ + x + 1. La crittografia a curve ellittiche e il problema del logaritmo discreto vivono all'interno di GF(p) e GF(p^k).
• Codici a correzione d'errore — I codici Reed-Solomon e BCH (usati in CD, codici QR, DVB-T, sonde spaziali Voyager) sono costruiti da polinomi su GF(2⁸) o GF(2^m).
• Design combinatori — I campi finiti permettono di costruire matrici di Hadamard, piani proiettivi e quadrati latini usati negli esperimenti statistici.
• Algebra computazionale — Gli algoritmi di fattorizzazione e riduzione modulare (Berlekamp, Cantor-Zassenhaus) sono formulati su campi finiti.
• Didattica della teoria dei numeri — Z_n, le radici primitive e i residui quadratici sono la porta d'accesso all'aritmetica modulare, RSA e Diffie-Hellman.

Domande frequenti

Quando Z_n è un campo?

L'anello modulare Z_n è un campo se e solo se n è primo. In tal caso ogni elemento non nullo è un'unità perché mcd(a, n) = 1 per ogni 0 < a < n. Quando n è composto, Z_n ha divisori dello zero ed è solo un anello, non un dominio.

Cos'è GF(p^k)?

GF(p^k), chiamato anche campo di Galois di ordine p^k, è l'unico campo finito con p^k elementi. I suoi elementi sono rappresentati come polinomi di grado inferiore a k su GF(p), con l'aritmetica eseguita modulo un polinomio irriducibile f(x) di grado k. Per ogni primo p e intero positivo k esiste esattamente un tale campo a meno di isomorfismi.

Cos'è un polinomio irriducibile e perché è necessario?

Un polinomio irriducibile su GF(p) è un polinomio che non può essere scomposto in polinomi di grado inferiore con coefficienti in GF(p). La riduzione modulo un polinomio irriducibile di grado k produce un anello quoziente che è un campo. Senza irriducibilità, il quoziente presenta divisori dello zero e non è un campo.

Cos'è un divisore dello zero?

Un elemento non nullo a in un anello è un divisore dello zero se esiste un elemento non nullo b tale che a · b = 0. In Z_n i divisori dello zero sono esattamente gli elementi a con mcd(a, n) maggiore di 1. I campi non hanno divisori dello zero, motivo per cui Z_n è un campo precisamente quando n è primo.

Cos'è l'ordine moltiplicativo di un elemento?

L'ordine moltiplicativo di un'unità a è il più piccolo intero positivo k tale che a^k è uguale a 1 nell'anello. Per il teorema di Lagrange questo ordine divide la dimensione del gruppo moltiplicativo: φ(n) per Z_n, o p^k − 1 per GF(p^k). Un elemento il cui ordine è pari alla dimensione dell'intero gruppo è chiamato radice primitiva o generatore.

Cosa fa un elemento primitivo di GF(p^k)?

Un elemento primitivo è un generatore del gruppo moltiplicativo GF(p^k)*, che è ciclico di ordine p^k − 1. Ogni elemento non nullo del campo può essere scritto come una potenza dell'elemento primitivo, il che rende possibili il logaritmo discreto, i codici BCH e la correzione degli errori Reed-Solomon.

Approfondimenti

• Aritmetica modulare — Wikipedia
• Campo finito — Wikipedia
• Radice primitiva modulo n — Wikipedia
• Funzione phi di Eulero — Wikipedia
• Polinomio irriducibile — Wikipedia