Division euclidienne entre deux polynômes

Discussions générales concernant les mathématiques.
[participation réservée aux membres inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
gronaze

Division euclidienne entre deux polynômes

Message non lu par gronaze »

Bonjour,

je bloque depuis vraiment longtemps sur la division d'un polynôme r[0][] par r[1][].
j'effectue mes calculs dans le corps de Galois GF(2^8) = GF(256).
http://www.sweegy.ch/documents/reports/ ... ler%20.pdf

Avec r[0][18] = 1 et le reste est nul. ça signifie r[0] = alpha^1 . x^18 = x^18 et
r[1][0] = 59
r[1][1] = 241
r[1][2] = 109
r[1][3] = 66
r[1][4] = 2
r[1][5] = 65
r[1][6] = 54
r[1][7] = 239
r[1][8] = 109
r[1][9] = 11
r[1][10] = 157
r[1][11] = 203
r[1][12] = 13
r[1][13] = 163
r[1][14] = 247
r[1][15] = 95
r[1][16] = 162
r[1][17] = 80
r[1][18] = 0
ce qui s'écrit r[1] = 59 + alpha^241 . X + alpha^109 . X^2 + ... + alpha^80 . X^17

Je recherche d'abord les monômes les plus élévés afin de calculer la valeur de alpha qui permet d'annuler le monome (le plus élevé) de r[1].

explications:
Ici les 2 monômes les plus élevés sont r[0][18] et r[1][17]. ils ont respectivement 18-17 = 1 degré d'écart. on va donc devoir multiplier K . X^(18-17) à r[1][17] afin d'annuler r[0][18].
Calcul de K:

Code : Tout sélectionner

if(r[0][18] > r[1][17])
		k = r[0][18] - r[1][17];
	else if(r[0][18] < r[1][17])
			k = r[0][18] + 255 - r[1][17];
		else k = 1;
rappel sur les opérations
l'addition lorsque l'on manipule des alpha se note: a++b = GF( GFI(a) ^ GFI(b) )
et la multiplication: a**b = a+b % 255

Je définis GF grâce au tableau de la page 7 du polycopié:
GF nous permet de passer de la forme décimale aux éléments, ex GF(10) = 9
et GFI nous permet de passer des éléments à la forme décimale, ex GFI(12) = 15. Ceci vous permet de comprendre le raisonnement car on travail sur GF(256) donc les tables ne sont pas les mêmes...

Bref revenons à nos moutons.
Je connais l'élément multiplicatif K qui permet de faire diminuer r[0] d'un degré.
Je multiplie ce K a chaque monôme de r[1]

Maintenant que j'ai fait ça, il ne me reste plus qu'a additionner ce que je viens de trouver au polynôme r[1]. Le résultat de cette addition nous donne un polynôme temporaire.

r[0] | r[1]
|_____
r_temp | Q
|
|

voila mais c'est pas très clair mais on visualise beaucoup mieux sur le poly en page 26-27

et je continue tant que le d°(r_temp) >= d°(r[1])


Voila si quelqu'un a déjà implémenté un bout de code permettant de faire une division euclidienne entre 2 polynômes, je serais intéressé de comparer mes résultats afin de réparer le bug que j'ai.
Sinon toute aide est la bienvenue parce que la je trouve pas ce qui va pas et ça m'énérve