Moltiplicazione di polinomi a coefficienti in un campo

[nochipfritz]

salve,
qualcuno potrebbe spiegarmi, possibilmente con un ESEMPIO, come si moltiplicano due polinomi a coefficienti nel campo $\mathbb{Z}_n[x]$?

Per esempio, immagino che $x^3 + 2x+1$ e $x+2$ siano in $\mathbb{Z}_3[x]$. Bene, come si moltiplicano in $\mathbb{Z}_3[x]$ ? Mi interessa capire il procedimento (e capire quando applicare le riduzioni modulari in tale procedimento)....per implementare un algoritmo.

[Ravok]

Bhè, $ZZ_3={0,1,2}$ o indifferentemente ${-1,0,1}$. quindi le moltiplicazioni e le addizioni vanno eseguite come in $ZZ$ ricordando che ragioniamo modulo $3$, e che quindi devi trasformare (non sempre) il risultato.
Esempio:
$2+2=1$ oppure $-1+(-1)=-2=1$
Nel tuo caso:
$(x^3 + 2x+1)(x+2)=x^4+2x^2+x+2x^3+x+2$
Ciao

PS per informazione, i polinomi stanno in $ZZ_3[x]$, i coefficienti stanno in $ZZ_3$

[nochipfritz]

Quindi se non ho capito male....un algoritmo potrebbe essere questo

siano $f, g, h$ tre vettori che rappresentano i coefficienti di 3 polinomi. E sia h il vettore che deve contenere il prodotto tra $f$ e $g$ allora, supponendo che inizialmente il vettore $h$ abbia tutti gli elementi settati a zero l'algoritmo sarebbe :


for i=0 to grado(f)
for j=0 to grado(g)
h[i+j] = (h[i+j] + (f*g[j]) mod n ) mod n
endfor
endfor

Domanda....se io ho

n = 5
f : 1 1 (che corrisponde a x+1)
g : 1 1 (che corrisponde a x+1)

perchè ottengo come h: 1 2 2 1
e non h : 1 2 1 ( cioè (x+1)^2)

C'è qualcosa di sbagliato nell' algoritmo?

[nochipfritz]

ecco forse è meglio che vi posto direttamente il codice java

int gradg1 = degg1();
int gradf1 = degf1();
for(i=0; i <=gradg1; i++)
for(j=0; j <= gradf1; j++)
{
k=i+j;
kk = (BigInteger) h1.get(k);
ii = (BigInteger) g1.get(i);
jj = (BigInteger) f1.get(j);
h1.add(k, kk.add(ii.multiply(jj).mod(n)).mod(n));
}

PS. il metodo add sul vettore h1 non indica somma....ma solo assegnamento

[Ravok]

Premettendo che non ne so niente di Java.. posso ragionare in C++ se vuoi, e mi sembra che il tuo algoritmo così come lo hai spiegato nel tuo penultimo post vada bene... il modulo n lo puoi mettere una volta sola, metterlo due volte è ridondante..
Ti consiglio di controllare la sintassi, magari sbagli qualcosa nei due cicli... di più non saprei dirti...
ciao ciao