exo spé maths en rapport avec la cryptographie
-
LLoris dernière édition par
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
-
Mmathtous dernière édition par
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]
-
LLoris dernière édition par
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] ?
-
Mmathtous dernière édition par
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]
-
Mmathtous dernière édition par
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]
-
LLoris dernière édition par
Donc il faut demontrer que 7n n'est pas congrus a 7n' pour prouver que les codages sont differents ?
-
Mmathtous dernière édition par
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]
-
LLoris dernière édition par
Euh oui, mais je ne vois pas du tout comment faire ce genre de demonstration ...
-
Mmathtous dernière édition par
7n ≡ 7n' [256] ⇔ 7n - 7n' est un multiple de 256.
Continue.
-
LLoris dernière édition par
donc 7(n-n') est un multiple de 256 donc n-n' est un multiple de 256 donc n ≡ n' [256] ?
-
Mmathtous dernière édition par
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 ...
-
Mmathtous dernière édition par
Je dois impérativement me déconnecter.
A+
-
LLoris dernière édition par
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
-
Mmathtous dernière édition par
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.
-
LLoris dernière édition par
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.
-
LLoris dernière édition par
Merci.