Inverso di un polinomio
Qualcuno sa come si risolve questo esercizio ?
Calcola l'inverso di x in Q(x) / (f) , con f = x(al quadrato) + x + 1
il risultato viene - (x+1) / (f)
Se qualcuno lo sa risolvere inserisca i passaggi intermedi!
Grazie
Calcola l'inverso di x in Q(x) / (f) , con f = x(al quadrato) + x + 1
il risultato viene - (x+1) / (f)
Se qualcuno lo sa risolvere inserisca i passaggi intermedi!
Grazie
Risposte
sai che proprio non ho capito cosa intende?
inanzitutto...cos'è Q(x)??un generico polinomio?
Marvin
inanzitutto...cos'è Q(x)??un generico polinomio?
Marvin
Con Q(x) Empty ha indicato l'anello dei polinimi a coeficenti in Q (anche se è più usuale indicarlo con Q[x]).
Trovere l'inverso di un polinomio vuol dire trovere quel polinnomio che moltiplicato per quello dato mi da l'dentità nel campo sonsiderato (in questo caso Q(x)/f che è effettivamente un campo perchè f è irriducibile in Q).
Cioè devi trovare quel polinomio q(x) tale che
x*q(x)-k*f(x)=1 dove k appertiene a Q* (insieme degli elementi invertibili di Q);
In generale è utile usare il teorema bi Bezout, ma in questo caso semplice basta osservare che si può scrivere:
x*q(x)=1+k*f(x) cioè x*q(x)=1+k*x^2+k*x+k ;
Scegliendo k=-1 si ricava:
x*q(x)=-x^2-x da cui si ottiene
q(x)=-(x+1).
Platone
Trovere l'inverso di un polinomio vuol dire trovere quel polinnomio che moltiplicato per quello dato mi da l'dentità nel campo sonsiderato (in questo caso Q(x)/f che è effettivamente un campo perchè f è irriducibile in Q).
Cioè devi trovare quel polinomio q(x) tale che
x*q(x)-k*f(x)=1 dove k appertiene a Q* (insieme degli elementi invertibili di Q);
In generale è utile usare il teorema bi Bezout, ma in questo caso semplice basta osservare che si può scrivere:
x*q(x)=1+k*f(x) cioè x*q(x)=1+k*x^2+k*x+k ;
Scegliendo k=-1 si ricava:
x*q(x)=-x^2-x da cui si ottiene
q(x)=-(x+1).
Platone
non era decisamente alla mia portata..
Ora non ho le facoltà mentali per studiarmelo
Domani ci proverò
E' facile che vi elenchi ulteriori quesiti ... tenetevi pronti
Vi ringrazio!
Ciao
Domani ci proverò
E' facile che vi elenchi ulteriori quesiti ... tenetevi pronti
Vi ringrazio!
Ciao
Ve ne do uno simile
Spiegatemi i passaggi perchè se non lo fate non ci capisco una "mazza"
ES. Calcola l'inverso di x^2 + 5x + 2 in Z7[x] / f , con f = x^3 + 3
Grazie a chi lo risolve.
Spiegatemi i passaggi perchè se non lo fate non ci capisco una "mazza"
ES. Calcola l'inverso di x^2 + 5x + 2 in Z7[x] / f , con f = x^3 + 3
Grazie a chi lo risolve.
Prima di fornire la soluzione al problema originario posto da Empty Head direi che prima è opportuno dare qualche definizione. Al pari di quanto avviene nel campo dei numeri interi un generico polinomio p(x) diviso per un polinomio f(x) fornisce un ‘quoziente’ q(x) e un ‘resto’ r(x), ovvero è…
p(x)= q(x)*f(x) + r(x) (1)
Analogamente a quanto avviene per i numeri interi, dalla (1) è possibile definire…
r(x) = p(x) mod [f(x)] (2)
… ossia r(x) è uguale a ‘p(x) modulo f(x)’. E’ possibile dimostrare che l’insieme dei polinomi ‘modulo f(x)’ costituiscono un campo moltiplicativo e f(x) è chiamato ‘polinomio generatore del campo’. Come in tutti i campi moltiplicativi ad ogni elemento del campo [escluso l’elemento nullo ] corrisponde un ‘inverso’ , ossia quell’elemento che moltiplicato per esso fornisce l’elemento ‘unitario’. Nel nostro caso se p(x) è un elemento del campo, il suo inverso i(x) sarà tale per cui…
p(x)*i(x)= 1 mod [f(x)] (3)
Se f(x) è un polinomio di grado n, tutti i polinomi ‘modulo f(x)’ saranno di grado inferiore o uguale a n-1…
Veniamo ora al problema posto da Empty Head. Il polinomio generatore del campo è f(x) = x^2+x+1 e il polinomio di cui si richiede l’inverso è p(x)=x. Indicando il polinomio inverso [di grado unitario in questo caso…] con i(x)= a1x+ao per la (1) si ha…
x*(a1x+ao)/(x^2+x+1) = (a1 x^2+ao x)/(x^2+x+1)=
a1+r(x)/(x^2+x+1) = a1+1/(x^2+x+1) (4)
Operando sulla (4) ed eguagliando i coefficienti dello stesso grado si ottiene il sistema di due equazioni in due incognite…
ao=a1
a1+1=0 (5)
… che risolto fornisce ao=-1 e a1=-1. Il polinomio cercato, l’inverso di x, è dunque i(x) = -x-1. L’altro esempio, quello ‘inventato’ da Empty Head, è un poco più difficile e lo lascio come esercizio per i ‘volonterosi’…
cordiali saluti
lupo grigio
p(x)= q(x)*f(x) + r(x) (1)
Analogamente a quanto avviene per i numeri interi, dalla (1) è possibile definire…
r(x) = p(x) mod [f(x)] (2)
… ossia r(x) è uguale a ‘p(x) modulo f(x)’. E’ possibile dimostrare che l’insieme dei polinomi ‘modulo f(x)’ costituiscono un campo moltiplicativo e f(x) è chiamato ‘polinomio generatore del campo’. Come in tutti i campi moltiplicativi ad ogni elemento del campo [escluso l’elemento nullo ] corrisponde un ‘inverso’ , ossia quell’elemento che moltiplicato per esso fornisce l’elemento ‘unitario’. Nel nostro caso se p(x) è un elemento del campo, il suo inverso i(x) sarà tale per cui…
p(x)*i(x)= 1 mod [f(x)] (3)
Se f(x) è un polinomio di grado n, tutti i polinomi ‘modulo f(x)’ saranno di grado inferiore o uguale a n-1…
Veniamo ora al problema posto da Empty Head. Il polinomio generatore del campo è f(x) = x^2+x+1 e il polinomio di cui si richiede l’inverso è p(x)=x. Indicando il polinomio inverso [di grado unitario in questo caso…] con i(x)= a1x+ao per la (1) si ha…
x*(a1x+ao)/(x^2+x+1) = (a1 x^2+ao x)/(x^2+x+1)=
a1+r(x)/(x^2+x+1) = a1+1/(x^2+x+1) (4)
Operando sulla (4) ed eguagliando i coefficienti dello stesso grado si ottiene il sistema di due equazioni in due incognite…
ao=a1
a1+1=0 (5)
… che risolto fornisce ao=-1 e a1=-1. Il polinomio cercato, l’inverso di x, è dunque i(x) = -x-1. L’altro esempio, quello ‘inventato’ da Empty Head, è un poco più difficile e lo lascio come esercizio per i ‘volonterosi’…
cordiali saluti
lupo grigio
Ho due domande per te Lupo Grigio
a1+r(x)
da dove esce?
e
ao = a1
a1+1= 0
come l' hai ottenuto ?
-------------------------------------------------
Nessuno sa risolvere l'esercizio di prima in Z7(x)?
a1+r(x)
da dove esce?
e
ao = a1
a1+1= 0
come l' hai ottenuto ?
-------------------------------------------------
Nessuno sa risolvere l'esercizio di prima in Z7(x)?
In effetti sono stato un poco ‘approssimativo’ e di questo chiedo scusa a Empty Head. Proviamo a impostare il problema in termini generali e cioè, definito il polinomio generatore f(x) di grado n e un polinomio p(x) del campo diverso dal polinomio nullo trovare i(x), il polinomio inverso di p(x). Ponendo i(x) nella forma…
i(x) = ao+a1*x+… a(n-1) * x^(n-1) (1)
… il problema si riduce al calcolo delle ai per i=0,1,…,n-1. Ricordando la formula generale per la divisone dei polinomi è …
p(x)*i(x)/f(x) = q(x) + r(x)/f(x) (2)
… dove q(x) è il ‘quoziente’ e r(x) è il ‘resto’. Dal momento che i(x) è il polinomio inverso di p(x) deve essere necessariamente r(x)=1. Si procede dunque nel modo seguente. Dati f(x) e p(x) si scrive il primo termine dell’equazione (2) nella forma…
p(x)*[ao+a1*x+…a(n-1)*x^(n-1)]/f(x) (3)
… e si sviluppa la divisione secondo la regola standard di Ruffini. In tal modo si ottengono i coefficienti di q(x) e r(x) in funzione delle ao,a1,…,a(n-1). Fatto questo si impone che, indicando con ro,r1,…,r(n-1) i coefficienti del polinomio resto soddisfino alla condizione ri= 1 per i=0, =0 per i diverso da 0. In tal modo si ha un sistema di n equazioni in n incognite che, risolto, fornisce le ai. I dettagli del calcolo a questo punto li lascio a voi…
cordiali saluti
lupo grigio
i(x) = ao+a1*x+… a(n-1) * x^(n-1) (1)
… il problema si riduce al calcolo delle ai per i=0,1,…,n-1. Ricordando la formula generale per la divisone dei polinomi è …
p(x)*i(x)/f(x) = q(x) + r(x)/f(x) (2)
… dove q(x) è il ‘quoziente’ e r(x) è il ‘resto’. Dal momento che i(x) è il polinomio inverso di p(x) deve essere necessariamente r(x)=1. Si procede dunque nel modo seguente. Dati f(x) e p(x) si scrive il primo termine dell’equazione (2) nella forma…
p(x)*[ao+a1*x+…a(n-1)*x^(n-1)]/f(x) (3)
… e si sviluppa la divisione secondo la regola standard di Ruffini. In tal modo si ottengono i coefficienti di q(x) e r(x) in funzione delle ao,a1,…,a(n-1). Fatto questo si impone che, indicando con ro,r1,…,r(n-1) i coefficienti del polinomio resto soddisfino alla condizione ri= 1 per i=0, =0 per i diverso da 0. In tal modo si ha un sistema di n equazioni in n incognite che, risolto, fornisce le ai. I dettagli del calcolo a questo punto li lascio a voi…
cordiali saluti
lupo grigio
Empty, ma il secondo lo hai davvero inventato tu?
Ad ogni modo, sempre se non ho sbagliato a fare i conti non esiste l'inferso di quel polinomio in Z7[x]/f.
Platone
Ad ogni modo, sempre se non ho sbagliato a fare i conti non esiste l'inferso di quel polinomio in Z7[x]/f.
Platone
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
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
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
cordiali saluti
lupo grigio
Z7[x] / (f)
è scritto così
è scritto così
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
Empty ora provo a farlo.
Platone
Ti ho mandato la soluzione per posta.
Platone
Platone
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)
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)
E tu sto papiro che hai scritto lo chiami modo semplice!??! [:D]
Platone
Platone
Sarà un po' lungo , ma è molto chiaro !
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 linear feedback shift register…
[img]http://digilander.libero.it/luposabatini/Lfsr3[/img]
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
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 linear feedback shift register…
[img]http://digilander.libero.it/luposabatini/Lfsr3[/img]
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
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo