Crypto - multiplication modulaire

[anima]

Bonjour,

Je suis en train de programmer une variante d'un algorithme assez connu, Rijndael. Cependant, cet algorithme (et ma variante) necessitent ce que les mathematiciens appellent une multiplication modulaire en GF(2^8).
Soit, , ou b est mon inconnue, et .

Jusqu'a present, j'ai utilise un algorithme assez lourd pour generer une table de conversion ("lookup table"). Cependant, il doit y avoir une methode plus simple pour trouver un inverse multiplicatif. Mon algorithme original est entierement base sur l'extension de l'algorithme d'Euclide, et n'est pas tres joli a voir.
Quelqu'un connait-il une methode plus efficace (au point de vue operations/bit) pour aboutir a l'inverse multiplicatif d'un nombre?

Merci.

[ffpower]

Pour toute inversion dans Z/nZ,Euclide me semble assez optimal non?

[anima]

Pour toute inversion dans Z/nZ,Euclide me semble assez optimal non?

Donc, il n'y a pas d'algo. plus efficace? (Dans un monde ideal, je prefererais avoir l'algorithme optimal, vu que j'utiliserai la fonction en question pour chaque byte d'un assez long message)

[ffpower]

Et bien,inverser a dans Z/nZ revient a trouver u et v tel que au+nv=1,autrement dit à faire bezout,donc l algo d euclide.Donc je ne pense pas qu il y ait plus efficace.Cela dit,ici vu que tu ne travaille qu avec un seul n(2^8),tu peut p-e crée directement une bonne fois pour toute une liste des inverses.Comme ca,t aura pas besoin de refaire les calculs a chaque fois..