Pagina 2 di 2

MessaggioInviato: 31/08/2005, 16:09
da Empty Head
E' un'esercizio trovato su un libro , ma non ha risultato!

Ti do questo , fallo come controprova , è simile

trova l'inverso di x^2 + x + 1 in Z7[x]/f , con f= x^3 + 3

il risultato dovrebbe venire 5x + 2

quando l'hai svolto , mandamelo x e-mail (fammi sto piacere)

grazie

ciao

MessaggioInviato: 31/08/2005, 16:13
da lupo grigio
Se devo essere sincero, una cosa che non mi è chiara è il significato dell'espressione 'Z7[x]/f'... non si tratta semplicemente del campo dei polinomi 'modulo f(x)'immagino... si prega di usare terminologia comprensibile anche ai 'non iniziati'... grazie...

cordiali saluti

lupo grigio

Immagine

MessaggioInviato: 31/08/2005, 16:17
da Empty Head
Z7[x] / (f)

è scritto così

MessaggioInviato: 31/08/2005, 17:29
da Platone
lupo grigio, anche secondo me non è scritto in modo correto, ma credo che signivichi (Z/7Z)/(f), cioè i polinomi modulo f(x) con coefficenti nel campo Z/7Z.

Empty ora provo a farlo.

Platone

MessaggioInviato: 31/08/2005, 18:28
da Platone
Ti ho mandato la soluzione per posta.

Platone

MessaggioInviato: 01/09/2005, 14:56
da Empty Head
Ringrazio sia Platone che Lupo Grigio per i suggerimenti dati.
Cerco di esporre quello che secondo il mio parere è il metodo più semplice per trovare l'inverso di un polinomio
in modo che , se nel futuro , qualcuno dovesse sbattere la testa su questo problema , trovi conforto in questo topic.


ok si parte!!!!!

cerco di spiegare lo svolgimento in modo che capisca chiunque!

- un polinomio 'a' diviso per un polinomio 'b' fornisce un quoziente 'q' e un resto 'r' --> a = b * q + r
- la divisione tra polinomi si applica con Ruffini
- attenti al modulo (lavorare in Z[x] non è come lavorare in Q[x] , in quest'ultimo è + semplice)


ESERCIZIO <<< >>> Troviamo l'inverso di x^2+5x+2 in Z7[x]/f dove f=x^3+3


p(x) = x^2+5x+2

f(x) = x^3+3

i(x) = ao+a1*x+… a(n-1) * x^(n-1) (è ciò che dobbiamo trovare)


1) trova il grado di i(x)


i(x) * p(x) = 1 mod[f(x)]


i(x) è l'inverso del polinomio , il suo grado sarà determinato dal grado di f(x)
infatti il grado di i(x) sarà uguale a n-1 dove n è il grado di f(x) ;


in questo caso...


i(x) = a0+a1x+a2x^2 perchè n=3


2) moltiplica i(x) * p(x) e dividi il prodotto per f(x) (con Ruffini)


i(x)*p(x) = a0x^2 + 5xa0 + 2a0 + x^3a1 + 5x^2a1 + 2xa1 + x^4a2 + 5x^3a2 + 2x^2a2


il resto che ottieni dalla divisione risulta (raccogliendo le x):


x^2(a0+2a2+5a1) + x(2a1+5a0-3a2) + 2a0 - 3a1 - a2



3) indico con r0 , r1 , r2 i coefficienti del polinomio resto:


a0+2a2+5a1 = r2

2a1+5a0-3a2 = r1

2a0-3a1-a2 = r0


questi devono soddisfare la condizione ri = 1 per i=0 e ri=0 per i diverso da 0 (i pedice...non è r*i) cioè...


a0+2a2+5a1 = r2 = 0 perchè i diversa da 0

2a1+5a0-3a2 = r1 = 0 perchè i diversa da 0

2a0-3a1-a2 = r0 = 1 perchè i uguale a 0


4) risolvi le tre equazioni in un sistema di 3 incognite ... ovviamente vai a trovare a0 a1 e a2 per poi inserirle in i(x)

dalla prima trovi a2,vai a sostituire a2 nella seconda e nella terza,dalla terza trovi a1,sostituisci a1 nella seconda in modo che
posso trovare a0 nella seconda , il quale mi viene -2/5 che in Z/7z è uguale a +1
successivamente trovi a1 e a2 , la prima risulta 3 e la seconda 6

5) inserisci appositamente in i(x) a0 a1 e a2

i(x) = 6x^2+3x+1

questo e l'inverso del polinomio di partenza p(x)

MessaggioInviato: 01/09/2005, 15:02
da Platone
E tu sto papiro che hai scritto lo chiami modo semplice!??! [:D]

Platone

MessaggioInviato: 02/09/2005, 13:02
da Empty Head
Sarà un po' lungo , ma è molto chiaro !

MessaggioInviato: 02/09/2005, 14:00
da lupo grigio
Eccellente e dettagliata l’esposizione fatta da Empty Head del metodo generale per trovare l’inverso di un polinomio modulo f(x) in un campo qualsiasi. Il metodo fornisce la soluzione nella totalità dei casi, anche se per polinomi di grado assai elevato, come ad esempio quelli usati in criptografia, può risultare di complessità computazionale immane. Nel caso si operi in campi a dimensione finita, ad esempio i campi di Galois, esistono degli algoritmi che agevolano di molto il calcolo. Prendiamo, a titolo di esempio, il GF 2^3, il quale è composto da polinomi di grado 3 in x i cui coefficienti appartengono alla classe degli interi modulo 2. Scegliendo come polinomio generatore…

g(x) = 1+x+x^3 (1)

… andiamo a calcolare le potenze distinte di x. Avremo…

x^0 =1
x^1= x
x^2=x^2
x^3=1+x
x^4=x+x^2
x^5=1+x+x^2
x^6=1+x^2
x^7=1 … (2)

E’ evidente che la successione delle potenze di x ha periodicità 7 ed è costituita dall’insieme dei polinomi del GF 2^3 diversi dal polinomio nullo. La sequenza illustrata dalla (2) può esser realizzata computazionalmente con lo schema rappresentato in figura, chiamato usualmente <i>linear feedback shift register</i>…

Immagine

Se go, g1 e g2 sono i coefficienti di un generico polinomio memorizzati nella struttura, la moltiplicazione per x è effettuata semplicemente operando uno shift. Osservando la (2) si nota che ad ogni polinomio è possibile associare il suo ‘logaritmo’, vale a dire l’esponente da dare ad x per avere quel polinomio. L’impiego del logaritmo consente di semplificare di molto le operazioni di prodotto, divisione e calcolo dell’inverso. In particolare dato un polinomio di esponente k, il polinomio inverso avrà esponente pari al complemento a 7 di k. Se per esempio p(x)= 1+x [esponente k=3…] il suo inverso avrà esponente 7-3=4 e sarà quindi i(x)=x+x^2. L’enorme semplificazione e velocizzazione di calcolo rispetto al procedimento generale prima descritto è del tutto evidente…

cordiali saluti

lupo grigio

Immagine