Inverse dans le champ de gallois GF(2^8)

[druduche]

Bonjour !

Je suis étudiant en informatique, et je cherche a faire un programme pour échelonner une matrice à coefficients dans GF(2^8) = GF(256)...
J'ai l'algorithme de base, selon le pivot de gauss, mais j'ai un problème concernant la division...

Comme je sais que c'est assez complexe de multiplier et de diviser la dedans, je définit dans mon programme des tableaux exp et log, qui contienne les puissances du générateur (2) et les logarithmes (en base 2) correspondants...
Ca simplifie beaucoup la chose, car du coup on a
a*b = exp(log(a) + log(b))

alors que normalement il faudrait passer par les polynômes, puis diviser par le générateur, etc...

le problème viens pour la division... je me suis dit, comme pour les modulos m, que diviser revenait a multiplier par l'inverse...
je trouve donc mon inverse comme suit :

on a a*a^-1 = 1
donc exp(log(a) + log(a^-1)) = 1
donc log(a) + log(a^-1) =0
donc a^-1 = exp(-log(a))...

ca marche bien SAUF pour 2 !
en effet, pour 2 on a 2^-1 = exp(-log(2)) = exp(-1) = exp(255), qui n'est pas définit selon ce pdf (page 17)

je ne vois pas du tout pourquoi.... hmmmm :triste:

Merci d'avance pour vos réponses !

[Doraki]

exp prend 255 valeurs différentes vu qu'il y a 255 nombres non nuls.
exp(0) = exp(255) et pas exp(256).

[druduche]

Merci bien !

Je vois pourquoi maintenant, mais je ne sais toujours pas comment trouver l'inverse de 2.... existe-t-il ? Ou dois-je passer par la division polynomiale ?

Merci d'avance! :++:

[Doraki]

ben 2^255 = 1 donc 2 * (2^254) = 1. 2^254 est l'inverse de 2.

[druduche]

Ah ben oui, ca a l'air tout simple ! :we:

Splendide, tu m'aides beaucoup !
Merci bien et bonne fin de journée ! :happy: