Cryptographie (Spé. Math. Terminale S.)

[Tetdoss]

Salut à tous, pour lundi j'ai un devoir maison de spé math à rendre sur la cryptographie. J'ai fait les 2 tiers du devoir mais là je commence à bloquer...

B) Le codage affine : Le codeur choisit deux entiers a et b. On code la lettre de rang x par celle de rang g(x), reste de la division euclidienne de ax + b par 26.
Le rang d'une lettre est compris entre 0 et 25 : A = 0, B = 1... Z = 25.

Je passe les questions 1 et 2 pour en venir à la 3 :

Dans les questions 3 et 4 on suppose que a est premier avec 26.

3)a) Montrer que si g(x) = g(x') alors x = x'. Je n'ai pas réussi à démontrer cela. Je tombe sur ax ;) ax' [26] mais c'est tout...

Ensuite on me demande d'en déduire que deux éléments différents ont des images différentes, je trouve ça évident à comprendre mais je n'arrive pas à le démontrer à l'aide de l'affirmation précédente.

b) Montrer qu'il existe un entier a' dans {0, 1, ... , 25} tel que aa' ;) 1 [26] , ça me fait penser au petit théorème de Fermat mais rien de plus...

La suite je pense pouvoir réussir.

Merci beaucoup d'avance.

[Kikoo <3 Bieber]

Salut à tous, pour lundi j'ai un devoir maison de spé math à rendre sur la cryptographie. J'ai fait les 2 tiers du devoir mais là je commence à bloquer...

B) Le codage affine : Le codeur choisit deux entiers a et b. On code la lettre de rang x par celle de rang g(x), reste de la division euclidienne de ax + b par 26.
Le rang d'une lettre est compris entre 0 et 25 : A = 0, B = 1... Z = 25.

Je passe les questions 1 et 2 pour en venir à la 3 :

Dans les questions 3 et 4 on suppose que a est premier avec 26.

3)a) Montrer que si g(x) = g(x') alors x = x'. Je n'ai pas réussi à démontrer cela. Je tombe sur ax ax' [26] mais c'est tout...

Ensuite on me demande d'en déduire que deux éléments différents ont des images différentes, je trouve ça évident à comprendre mais je n'arrive pas à le démontrer à l'aide de l'affirmation précédente.

b) Montrer qu'il existe un entier a' dans {0, 1, ... , 25} tel que aa' 1 [26] , ça me fait penser au petit théorème de Fermat mais rien de plus...

La suite je pense pouvoir réussir.

Merci beaucoup d'avance.

Yo,

Pour la 3)a), t'arrives à

Cela s'écrit autrement ce qui est équivalent à .
D'après le théorème de Gauss, Nous écrivons et sachant que x et x' appartiennent à , qu'en déduis-tu ?

[Kikoo <3 Bieber]

Bah si t'arrives pas à le voir, utilise des potatoes (loooool) !

Soit la fonction tq

Cette fonction est injective, grâce à la propriété que l'on vient de démontrer au-dessus. Cela équivaut à dire que mais je sais pas si ma rédaction est bonne...

EDIT : Voilà, maintenant, c'est bon

[Tetdoss]

Merci beaucoup pour tes réponses Kikoo :)

En fait c'était pas si dur en effet, je tombe sur x ;) x' [26] et comme 0 <= x < 26 alors x = x' :)

En ce qui concerne ton implication de ta 2ème réponse, je crois que c'est l'inverse qu'il faut trouver :

x != x' => g(x) != g(x')

EDIT : en fait c'est la contraposée donc c'est bon :D

Je vais essayer de continuer.

[Kikoo <3 Bieber]

Ok, je vais te laisser réfléchir un peu :zen:

Petit indice, pas besoin de notre ami Fermat, juste du pote Bézout ;)

[nana32]

svp pouvez vous me dire comment crée une discussion je ny arrive pas merci et excuser moi

[Kikoo <3 Bieber]

svp pouvez vous me dire comment crée une discussion je ny arrive pas merci et excuser moi

Ok
Tu vas dans la rubrique qui t'intéresse (primaire-collège, lycée, supérieur, ...) et normalement, en haut à gauche, ya un bouton "nouvelle discussion". Tu cliques dessus et mamie Irma va trouver ton bonheur :zen:

[Tetdoss]

Je crois que je m'avoue vaincu par la question b), en fait la tournure de la question fait que je ne vois pas du tout par où commencer :(

Cette question doit pouvoir m'aider à trouver ensuite la formule de décodage, càd une expressions de x en fonction de a, b, a' et g(x)...

[Kikoo <3 Bieber]

Je crois que je m'avoue vaincu par la question b), en fait la tournure de la question fait que je ne vois pas du tout par où commencer

Cette question doit pouvoir m'aider à trouver ensuite la formule de décodage, càd une expressions de x en fonction de a, b, a' et g(x)...

Ouais. Bon, pour commencer, nous réécrivons la relation de congruence en
Cela revient à . Or nous savons bien que comme , alors d'après le théorème de Bézout, tq . Ben justement, ici il existe un couple qui satisfait cette condition ! Nous avons prouvé l'existence de cet entier a'.

[Tetdoss]

Oua ! Bravo Kikoo :we: , je n'aurais pas pensé à utiliser Bézout pour montrer l'existence d'un entier ! Je n'avais même pas pensé de réécrire la relation de congruence avec le k. Merci beaucoup.

Plus qu'à trouver la formule de décodage, j'y travaille, ce serait bien que j'en trouve au moins une question ^^

[Kikoo <3 Bieber]

Oua ! Bravo Kikoo :we: , je n'aurais pas pensé à utiliser Bézout pour montrer l'existence d'un entier ! Je n'avais même pas pensé de réécrire la relation de congruence avec le k. Merci beaucoup.

Plus qu'à trouver la formule de décodage, j'y travaille, ce serait bien que j'en trouve au moins une question ^^

Pfff t'as quand même fait les deux tiers, nan ? :p T'inquiète pas, moi aussi chuis une tête d'os en spé (surtout dans la partie similitudes :triste:) mais je tends à progresser !

[Tetdoss]

Ok mais les 2 tiers c'était quand même plus simple, j'avais pas besoin des copains mathématiciens.

Ok, bon, je vais péter un câble maintenant ><

Ce que je sais :

g(x) ;) ax + b [26]
aa' ;) 1 [26]
pgcd(a, 26) = 1

Ok alors j'obtiens :

ax ;) g(x) + aa' - b - 1 [26] Oooh Yeah !!!

Mouais ça sert à rien en fait... J'ai trouvé une égalité avec des k mais ça va pas m'aider à décoder si il y a des k dans mon égalité...

Je crois bien que je suis une tête d'os tout court.

[Kikoo <3 Bieber]

[quote="Tetdoss"]Ok mais les 2 tiers c'était quand même plus simple, j'avais pas besoin des copains mathématiciens.

Ok, bon, je vais péter un câble maintenant ><)

[Tetdoss]

[quote="Kikoo <)[/quote]

Oh ne t'inquiète pas pour le délais et merci encore, je faisais les questions d'après. J'ai un peu du mal à suivre ton raisonnement à la fin.
Ta réponse est évidente mais juste une chose que je ne comprends pas : aa' 1 mod 26 et tu dis que a' = inv(a) alors qu'on ne peut pas diviser dans les congruences.

[Kikoo <3 Bieber]

Oh ne t'inquiète pas pour le délais et merci encore, je faisais les questions d'après. J'ai un peu du mal à suivre ton raisonnement à la fin.
Ta réponse est évidente mais juste une chose que je ne comprends pas : aa' 1 mod 26 et tu dis que a' = inv(a) alors qu'on ne peut pas diviser dans les congruences.

J'ai pas divisé ^^ En fait j'avais eu une question similaire lors d'un contrôle, et en arithmétique modulaire, on définit à un entier a un entier tel que , avec ...
Il s'agit d'un entier !! On multiplie un entier par un entier, on ne divise pas (quelle horreur !!).
Par exemple... l'inverse de 4 modulo 5 est 4 car

[Tetdoss]

Ah ça me rassure alors mais je n'ai jamais vu ça :O Pourtant j'ai fini le chapitre des congruences depuis bien longtemps. Mais si c'est la seule méthode, pourquoi se priver...

[Kikoo <3 Bieber]

Ah ça me rassure alors mais je n'ai jamais vu ça :O Pourtant j'ai fini le chapitre des congruences depuis bien longtemps. Mais si c'est la seule méthode, pourquoi se priver...

Je t'ai rien appris Juste que a' s'appelle inv(a)...
D'ailleurs je l'ai vu en contrôle ça, et pas en cours

[Tetdoss]

Ah ok, alors c'est bon :D Merci beaucoup je ne t'embête plus :D

[Kikoo <3 Bieber]

Ah ok, alors c'est bon Merci beaucoup je ne t'embête plus

Mais non, t'inquiètes Ca me fait du bien de réviser un peu !

[sad13]

L'injectivité n'est pas au programme en Ts mais on peut dire dire que deux réels différents par stricte monotonie ont deux images différentes !