bonjour à tous,
 
je suis en train de bloquer sur un exercice que j'ai a faire pour lundi la.  
 
On note C la fonction de cryptage, qui à tout n entier appartenant à [0;255]associe le reste de la division de 7n par 256. soit C(n) ce reste.
 
1) montrer que si C(n)=C(p) alors 7(n-p) congru à 0 (256)
 
je suis parti comme ca:
 
soit 7n+r congru a 0 (256)
      7p+r congru à 0 (256)
       
      7n-7p congru à 0 (256)
      7(n-p) congru à 0 (256)
 
ca suffit comme rédaction? je sias meme pas si c'est juste, les congruences je comprends pas bien, je fais des choses sans vraiment savoir ce que je fais.
 
2) En déduire que n=p . justifier que le codage est valide (on veut s'assurer que le codage d'un nombre n et p ne soient pas identiques)
 
je serais parti comme ca :
7n+r=256
7p+r=256
 
on a alors 7n-7p=0 donc n=p
 
mais je sais pas si c'est la bonne méthode, car ils marquent en déduire, je refais un autre raisonnement :s
 
3) vérifier que 183 * 7 congru a 1 (256) et en déduire que 183 * (7n) congru a n (256)
 
183*7=1281 et 1281 est congru a 1 (256)
 
 
183*7*n congru a 1*n (256) donc 183*7n congru a n (256)
 car si a congru a b (m) alors ax congru a bx (m)
 
4) expliquer pourquoi la fonction D, qui associe à k le reste de la division de 183k par 256, assure le décryptage attendu.
 
aucune idée sur quoi partir

Tu écris : "les congruences je comprends pas bien, je fais des choses sans vraiment savoir ce que je fais."
La première chose à faire, avant les exercices, c'est comprendre. Ce n'est pas très compliqué. Tu connais depuis longtemps la division euclidienne, dividende entier, diviseur entier, quotient entier et reste entier PLUS PETIT QUE LE DIVISEUR. Si je divise 29 par 4, le quotient euclidien est 7 et il reste 1   (29=7*4 + 1). Si je divise 22 par 4, quotient 5, reste 2 (22=5*4 + 2). 29 et 22 n'ont pas le même reste dans la division par 4. Mais une infinité de nombres ont le même reste que 29 dans la division par 4 (1, 5, 9, 13, 17, 21 etc).
Or dans la division euclidienne le reste entier doit être plus PLUS PETIT QUE LE DIVISEUR donc dans la division par 4 les restes possibles sont au nombre de 4 ( 0, 1, 2 et 3).
On démontre que la relation "a même reste dans la division par 4" est une relation d'équivalence, donc elle forme des classes d'équivalence, chaque classe étant formée de tous les nombres ayant même reste dans la division par 4. Il y a donc 4 classes  
0, 4, 8, 12 ... etc    qui ont pour reste 0
1, 5, 9, 13 ... etc    qui ont pour reste 1
2, 6, 10, 14 ... etc   qui ont pour reste 2
3, 7, 11, 15 ... etc   qui ont pour reste 3
 
Si deux nombres sont dans une même classe, on dit qu'ils sont congrus modulo 4  (cela veut dire "ils ont le même reste dans la division euclidienne par 4" ).
 
Dans ton problème le diviseur est 256 donc il y a 256 classes.
 
Le mieux pour comprendre ce que tu démontres, c'est d'utiliser la définition du quotient euclidien que je te rappelais plus haut  
dividende = quotient * diviseur + reste .  Pour la première question  7n = q1 * 256 + C(n)   à toi pour la suite.

7p=q2 * 256 + C(p)
 
si C(p) = C(n)  
on a  
 
7n=q1 * 256 + C(n)
7p=q2 * 256 + C(n)
 
7n-7p=(q1-q2)*256
avec q1-q2 appartient a Z
 
ca suffit ca pour la question 1 ?

7 en facteur dans le premier membre et j'écrirais "+ 0" dans le 2e membre pour bien souligner ce reste 0.

ok, je refais la suite plus tard dans la soirée pour voir ^^

je vois pas quoi faire por la secnde

pense au théorème de Gauss. A quelles conditions 7 et n-p sont-ils premiers entre eux ? Dans chacun des cas de figures tu peux déduire qu'alors 256 doit diviser n-p...

Je ne pense pas que ce soit la bonne réponse!

Relis l'énoncé : "n entier appartenant à [0;255]" combien y a-t-il de nombres congrus à 0 modulo 256 dans cet intervalle ?
Si n appartenait à N ou à [0,10000] ce serait évidemment différent.

ouis, bé, sincérmeent, c'est ce qui m'est venu en tete mais ca fait pas vraiment démonstration de math de dire qu'il n'y a que 0 qui est congru a 0 modulo 256 entre  pour 0<n<255 ...
 
comme quoi, je suis encore plus bete que je le pensais, va falloir que je rédige bien ca  mais ok, cette idée la je l'avais.
 
pour la 3ème, est ce que mon raisonnement est juste?

 
Tu affirmes "1281 est congru a 1 (256)", il faut le prouver en écrivant que 1281 = q*256 + 1   (en mettant la valeur de q)
Ensuite, on peut multiplier les 2 membres d'une égalité par un même nombre.

a il faut le prouver?  
il y avait marqué vérifié ^^ je pensais pas qu'il fallait détailler oulala je vais me chopper un beau 6/7 heureusement qu'il y aura la géométrie dans l'espace, meme si jamais dans ma vie j'aurai cru dire que la géométrie allait m'aider

Désolé kchaos, je pensais que tu répondais à la 2. Pour la 1, l'utilisation du lemme de gauss est pertinent.

Bon, je donne la solution:
On note C la fonction de cryptage, qui à tout n entier appartenant à [0;255]associe le reste de la division de 7n par 256. soit C(n) ce reste.  
 
1) montrer que si C(n)=C(p) alors 7(n-p) congru à 0 (256)  
C(n)=C(p) donc 7n=7p mod (256), le reste de la différence étant égal au reste de la différence du reste, en soustrayant 7p on obtient 7(n-p)=0 mod (256)
 
2) En déduire que n=p . justifier que le codage est valide (on veut s'assurer que le codage d'un nombre n et p ne soient pas identiques)  
7(n-p)=0 mod(256) ce qui veut dire que 256 divise 7(n-p).  
Comme pgcd(7,256)=1, 256 divise n-p (lemme de gauss)
donc n-p=0 mod(256)
 
Etant donné que 0<=n<256 et 0<=p<256, n=p
 
3) vérifier que 183 * 7 congru a 1 (256) et en déduire que 183 * (7n) congru a n (256)  
 
183*7=1281 et 1281 est congru a 1 (256)
 
le reste du produit étant égal au reste du produit du reste, le reste du produit de 183 x 7  par n est le reste du produit du reste de 183 x 7 par le reste de n, c'est à dire le reste du produit de 1 par n, ou encore n.
donc 183 * (7n) congru a n (256)
 
4) expliquer pourquoi la fonction D, qui associe à k le reste de la division de 183k par 256, assure le décryptage attendu.
 

D(C(n))= D(7(n))=183 x 7 x n = n (256)
 
On vérifie ainsi que D est la fonction inverse de la fonction de cryptage C. C'est donc, par définition la fonction de décryptage...

Pour en rajouter, tu peux dire qu'on a un système de cryptage assymétrique où la clé de cryptage est (7,256) la clé de décryptage est (183,256)