Forum de mathématiques - Bibm@th.net

Cracky

Membre

Inscription : 12-05-2011

Messages : 14

Congruence, cyptographie

Bonjour,

J'ai besoin d'aide, dans mes cours de cryptographie il y a beaucoup d’arithmétique. Et pour moi ça date un peu.

Je dois résoudre ceci : [tex] ( 25^{6}*76-8100)mod8 [/tex].

La consigne dit que le résultat doit être entre 0 et 7 ... Honnêtement, je sais que "ça ne se fait pas" trop ici de demander une solution, mais je ne sais pas du tout comment faire ! Je maîtrise quelques outils de l’arithmétique, comme Euclide, pgcd, ppcm, les congruences je m'en sort pas mal mais là je vois pas du tout "l'astuce" pour trouver ça.

Merci beaucoup d'avance a vous :)

edit : oups je m'etais trompé dans l'operation

Dernière modification par Cracky (24-03-2013 01:41:37)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Congruence, cyptographie

Bonjour,

La consigne dit que le résultat doit être entre 0 et 7

Curieuse consigne, car quel que soit le nombre dont on cherche le reste dans la division par 8, le reste sera toujours compris entre 0 et 7 inclus...

Je vais essayer de rester simple et de n'utiliser que des notions de base.
Libre après à quelqu'un d'autre, quand tu auras répondu, de prendre de la hauteur...
Soient deux nombres a et b supérieurs à 8...
On peut les les écrire [tex]a=8d_1+r_1[/tex] et[tex] b=a=8d_2+r_2[/tex]
D'où
Quid de a+b ?
[tex]a+b = 8d_1+r_1+8d_2+r_2=8(d_1+d_2)+(r_1+r_2)[/tex]
Le reste est la somme des restes... modulo 8 si cette somme est supérieure ou égale à 8...

Et
[tex]a\times b=(8d_1+r_1)(8d_2+r_2)=64d_1d_2+8d_1r_2+8d_2r_1+r_1r_2 =8(8d_1d_2+d_1r_2+d_2r_1)+r_1r_2[/tex]
D'où il ressort que r1 et r2 étant les restes de a et b dans la division par 8, le reste du produit a*b dans la division par 8 est le produit des restes r1r2, et s'il est supérieur ou égal à 8, [tex](r_1r_2)\mod 8[/tex]
C'est normal  : [tex]a \times b = \underbrace{a + a + \cdots+ a}_{b\;fois}[/tex]

Ce qui est vrai de la multiplication est vrai de la puissance : [tex]a^6=a\times a \times a \times a \times a \times a[/tex]...

Ça te va ?

@+