exo spé maths en rapport avec la cryptographie

Bonjour,

j'aurai besoin d'aide pour une question, et d'un petit rappel sur les congruences.
Tout d'abord, quand on sait que par exemple a ≡ b [c] , peut-on multiplier des deux côtés par un mm nombre n tel que an ≡ bn [c] ?

L'exo porte sur le codage ASCII, on admet que le code des caractéres alphanumériques utilisés est un entier n tel que 0 ≤ n ≤ 255. A chaque nombre de la ligne de codage ASCII qui code le message "le facteur sonnera trois fois." on associe le reste de la division de 7n par 256. On cherche alors à demontrer qu'à deux entiers differents sont associés deux codages differents par la fonction precedente.

Merci d'avance, j'espere avoir été claire...
Loris

Bonjour,
il est évident que si a ≡ b [c] alors pour tout entier n : an ≡ bn [c]
Mais la réciproque est fausse
sauf cas particuliers.
Ainsi : 24 ≡ 213 [6] , mais 4 n'est pas congru à 13 modulo 6.

Dans ton problème, on se trouve précisément dans un cas où on peut " diviser ".
Tu dois démontrer que si 7n ≡ 7n' [256] , alors n ≡ n' [256]
Il en résultera évidemment que n = n' puisqu'ils sont tous deux dans l'intervalle
[0 ; 255]

Me revoila dans la partie terminale , fibonacci c'était pour mon frere...
Donc pour le rappel merci , mais je comprends pas pourquoi on doit demontrer que 7n ≡ 7n' [256] ?

Ton application est de la forme : n → f(n) = 7n [256]
Tu dois démontrer que deux entier différents ont des images différentes :
n ≠ n' ⇒ f(n) ≠ f(n')
On raisonne par contraposée : si f(n) = f(n') , alors on doit avoir n = n'.
f(n) = f(n') se traduit par 7n ≡ 7n' [256]

Je précise : tu ne dois pas démontrer que 7n ≡ 7n' [256], tu dois démontrer que
Si7n ≡ 7n' [256] , alors n ≡ n' [256]

Donc il faut demontrer que 7n n'est pas congrus a 7n' pour prouver que les codages sont differents ?

Les messages ont dû se croiser : je reprends:
mathtous
Ton application est de la forme : n → f(n) = 7n [256]
Tu dois démontrer que deux entier différents ont des images différentes :
n ≠ n' ⇒ f(n) ≠ f(n')
On raisonne par contraposée : si f(n) = f(n') , alors on doit avoir n = n'.
f(n) = f(n') se traduit par 7n ≡ 7n' [256]
Citation
Je précise : tu ne dois pas démontrer que 7n ≡ 7n' [256], tu dois démontrer que Si 7n ≡ 7n' [256] , alors n ≡ n' [256]

Euh oui, mais je ne vois pas du tout comment faire ce genre de demonstration ...

7n ≡ 7n' [256] ⇔ 7n - 7n' est un multiple de 256.
Continue.

donc 7(n-n') est un multiple de 256 donc n-n' est un multiple de 256 donc n ≡ n' [256] ?

Tu vas trop vite : tu oublies le 7.
Tu dois utiliser pour conclure un célèbre théorème.
7(n-n') est un multiple de 256 autrement dit, 256 est un diviseur de 7(n - n').
Or 256 et 7 ...

Je dois impérativement me déconnecter.
A+

256 et 7 sont premiers entre eux, donc d'aprés le théoreme de Gauss etc ? Mais en quoi ca justifie la question?

Merci, à plus tard.
Loris

Citation
Tu dois démontrer que si 7n ≡ 7n' [256] , alors n ≡ n' [256]
Il en résultera évidemment que n = n' puisqu'ils sont tous deux dans l'intervalle
[0 ; 255]
On a donc démontré que si 7n ≡ 7n' [256] alors n ≡ n' [256]
Or n et n' sont tous deux entre 0 et 255, donc s'ils sont congrus modulo 256, ils sont égaux.
En résumé , f(n) = f(n') ⇒ n = n'
Et donc : n ≠ n' ⇒ f(n) ≠ f(n') : deux éléments différents ont des images ( i.e. des codages ) différents.

Ah d'accord! J'ai enfin compris merci beaucoup (la signification du i.e. ? )

Encore merci.
Loris

En l'absence de mathtous Wikipédia te répondrait que

id est est une expression latine et signifie « c’est-à-dire ». Son abréviation est souvent employée : i. e.

Merci.