Algoritmo di Berlekamp e MCD negli interi di Gauss
Salve a tutti, sono nuovo nuovo su questo forum, spero di scrivere nella sezione giusta! 
Ho un paio di problemini che non riesco a risolvere, si tratta di due esercizi.
Esercizio 1: si consideri l'anello R = F2[X]/(X^4 + X^3 + X^2 + X + 1)
i) Calcolare la cardinalità di R.
ii) R è un campo? E' un dominio?
Esercizio 2: calcolare il massimo comun divisore in $ ZZ $['i] tra 12 + 21i e 7 + 21i, e determinare la combinazione lineare a coefficienti in $ ZZ $['i] che lo produce.
Note: con F2[X] intendo l'anello dei polinomi a coefficienti in $ ZZ $/2$ ZZ $
I miei dubbi riguardano prima di tutto l'algoritmo di Berlekamp... qualcuno sa darmi una prova di procedimento... cioè. cosa devo fare per vedere se una funzione è irriducibile? Dopo che ho trovato la matrice che rappresenta il polinomio come procedo? Calcolando il rango in che modo...?
i) Poi, nel primo esercizio è giusto procedere verificando che X^4 + X^3 + X^2 + X + 1 sia irriducibile in F2[X] per poi, nel caso lo fosse, concludere che il quoziente è isomorfo a un campo e quindi ha cardinalità p^2 (nel nostro caso 2^4) oppure c'è un altro modo per trovare la cardinalità?
ii) Nel secondo esercizio invece suppongo si debba procedere tramite l'algoritmo di Euclide ma come lo applico agli interi di Gauss, come trovo i resti ecc.?
Grazie a chiunque mi risponderà... mi preme soprattutto trovare una specie di ricetta per l'algoritmo di Berlekamp da applicare per verificare la non riducibilità di un polinomio.
Saluti,
Nicola.
Ho un paio di problemini che non riesco a risolvere, si tratta di due esercizi.
Esercizio 1: si consideri l'anello R = F2[X]/(X^4 + X^3 + X^2 + X + 1)
i) Calcolare la cardinalità di R.
ii) R è un campo? E' un dominio?
Esercizio 2: calcolare il massimo comun divisore in $ ZZ $['i] tra 12 + 21i e 7 + 21i, e determinare la combinazione lineare a coefficienti in $ ZZ $['i] che lo produce.
Note: con F2[X] intendo l'anello dei polinomi a coefficienti in $ ZZ $/2$ ZZ $
I miei dubbi riguardano prima di tutto l'algoritmo di Berlekamp... qualcuno sa darmi una prova di procedimento... cioè. cosa devo fare per vedere se una funzione è irriducibile? Dopo che ho trovato la matrice che rappresenta il polinomio come procedo? Calcolando il rango in che modo...?
i) Poi, nel primo esercizio è giusto procedere verificando che X^4 + X^3 + X^2 + X + 1 sia irriducibile in F2[X] per poi, nel caso lo fosse, concludere che il quoziente è isomorfo a un campo e quindi ha cardinalità p^2 (nel nostro caso 2^4) oppure c'è un altro modo per trovare la cardinalità?
ii) Nel secondo esercizio invece suppongo si debba procedere tramite l'algoritmo di Euclide ma come lo applico agli interi di Gauss, come trovo i resti ecc.?
Grazie a chiunque mi risponderà... mi preme soprattutto trovare una specie di ricetta per l'algoritmo di Berlekamp da applicare per verificare la non riducibilità di un polinomio.
Saluti,
Nicola.
Risposte
Per quel che riguarda il primo esercizio,
$F_2[x]$$/$$(x^4+x^3+x^2+x+1)$
devi far vedere che il polinomio è irriducibile (non ha radici, quindi non ha fattori lineari, e poi con un metodo che vuoi, tipo un sistema, non ha fattori di secondo grado). Di sicuro non mi metterei a usare Berlekamp in questo caso.
quindi adesso dovrebbe essere finito l'esercizio, dipende da cosa sai.
la cardinalità è abbastanza facile, perchè puoi vedere $F_2[x]$$/$$(x^4+x^3+x^2+x+1)$ come spazio vettoriale su $F_2$
e quindi avrà cardinalità $2^4$.
il fatto che sia un dominio di integrità risulta facilmente perchè non ci sono 0-divisori, in quanto il polinomio è irriducibile.
poi è anche un campo proprio perchè il polinomio è irriducibile, e questo è un risultato che dovresti aver visto dalla teoria se hai trattato un po' i campi finiti.
$F_2[x]$$/$$(x^4+x^3+x^2+x+1)$
devi far vedere che il polinomio è irriducibile (non ha radici, quindi non ha fattori lineari, e poi con un metodo che vuoi, tipo un sistema, non ha fattori di secondo grado). Di sicuro non mi metterei a usare Berlekamp in questo caso.
quindi adesso dovrebbe essere finito l'esercizio, dipende da cosa sai.
la cardinalità è abbastanza facile, perchè puoi vedere $F_2[x]$$/$$(x^4+x^3+x^2+x+1)$ come spazio vettoriale su $F_2$
e quindi avrà cardinalità $2^4$.
il fatto che sia un dominio di integrità risulta facilmente perchè non ci sono 0-divisori, in quanto il polinomio è irriducibile.
poi è anche un campo proprio perchè il polinomio è irriducibile, e questo è un risultato che dovresti aver visto dalla teoria se hai trattato un po' i campi finiti.
Grazie mille.
E per quanto riguarda il secondo esercizio? Come applico Euclide agli interi di Gauss?
Poi se qualcuno ci riesce mi piacerebbe capire come usare l'algoritmo di Berlekamp magari con un esempio pratico perchè dal libro di teoria non riesco a capire come usarlo... ci girano intorno e mi perdo in nozioni teoriche che non riesco ad applicare agli esercizi
Grazie in anticipo.
E per quanto riguarda il secondo esercizio? Come applico Euclide agli interi di Gauss?
Poi se qualcuno ci riesce mi piacerebbe capire come usare l'algoritmo di Berlekamp magari con un esempio pratico perchè dal libro di teoria non riesco a capire come usarlo... ci girano intorno e mi perdo in nozioni teoriche che non riesco ad applicare agli esercizi
Grazie in anticipo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo