Crypto - multiplication modulaire

Discutez d'informatique ici !
anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 13:00

Crypto - multiplication modulaire

par anima » 20 Nov 2008, 18:03

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
Membre Complexe
Messages: 2542
Enregistré le: 13 Déc 2007, 06:25

par ffpower » 20 Nov 2008, 18:31

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

anima
Membre Transcendant
Messages: 3762
Enregistré le: 15 Sep 2006, 13:00

par anima » 20 Nov 2008, 18:42

ffpower a écrit: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
Membre Complexe
Messages: 2542
Enregistré le: 13 Déc 2007, 06:25

par ffpower » 20 Nov 2008, 19:25

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..

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 2 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite