maths spé dns

[meimona]

bonjour a tous ,

voila je me presente je suis une juene lycéenne en terminale scentifique qui a pris spé maths et jeprouve quelque difficulté dans cette matiere...

voici un dns qui nous a été donné la semaine passé c'est a dire avant le bac blanc , donc c par manque de comprehension mais surtout de temps que jai denorme difficultés .

je remercie par avance tout ceux qui maideront et ceux qui me liront bien evidemment.

jajoute que le sujet est long mais les questions rapides...

cryptographie affine

A. Le codage affine

pour transmettre un message secret , on utilise la procedure suivante :

.A toute lettre de l'alphabet , on associe le nombre lu dans le tableau ci-dessous:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

.soit x le nombre obtenu a partir de la lettre de depart . on calcule y=ax+b.

(le couple d'eniers (a;b) ou a different de 0, s'apelle la clé du codage)

.on calcule ensuite c(x) , reste de la division de y par 26.

.enfin on associe a c(x) la lettre correspondante par lectureinverse du tableau.

1.cas a =1

Dans ce cas , le codage se resume à un décalage.

Quel mathematicien se cache derriere "yxkftm"(clé(1;19))?

2.quelques exemples de clé

a.coder votre prenom avec la clé (7;17).

b.verifier que si "a "est congru a "a'" modulo 26 et "b" congru a "b'" modulo 26 , les codes obtenus avec les clés (a;b) et (a';b') sont identiques.

c.de combien de clés dispose-t-on en prenant 1 inferieur ou egale à "a" inferieur ou egale à 25 et 0 inferieur ou egale à b inferieur ou egale à 25 ?

d.on prend pour clé ( 2;13) . recopier et completer le tableau suivant:

mot initial E N T I E R

code x 4

2x+13 21

c(x) 21

mot codé v

quel probleme apparait dans le codage ci-dessus?

B.Decodage

1.dans le cas d'un codage affine de clé (7;17), cherchons une lettre dont le codage final soit b.

a) a l'aide de l'algorithme d'Euclie , trouver deux entiers u et v tels que 7u-26v=1

Justifier que 7u soit congru a 1 modulo 26.

B) soit x le code initial de la lettre cherchée. demontrer que x verifie (E): 7x est congru à -16 modulo 26

en deduire que x est congru a -16u modulo 26.

c)en deduire l'entier x compris entre 0 et 25 solution de (E) puis la lettre cherchée

2. expliquez pourquoi la methode ci-dessus assure le decodage de nimporte quelle lettre dés qu'on choisit une clé (a;b) telle que a soit premiere avec 26.

[philippe]

Bonsoir,

A.

Voici donc le processus:

une lettre "X" correspond à un nombre x

ensuite on calcule : y=ax+b mod(26)

y correspond donc à la lettre "Y"

A1

clé de codage (1;19).

y=x+19(26)

le nom codé est : YXKFTM

soit tu fais un tableau comme j'ai fait (voir plus bas)

soit tu calcules:

on cherche x tq 24=x+19(26)

on trouve x=5(26)

c'est F

en faisant de même tu trouvera FERMAT.

2a tu regardes mon tableau.

ex : jean se code en ctre

2b si a=a'(26) et b=b'(26)

alors ax=a'x(26)

puis ax+b=a'x+b'(26)

(rappel : si a=a'(n) et b=b'(n)

alors a+a'=b+b'(n)

et aa'=bb'(n))

si tu n'es pas convaincue:

a=a'(26) signifie (il existe A) a=a'+26A

b=b'(26) signifie (il existe B) b=b'+26B

donc

ax+b=(a'+26A)x+(b'+26B)=a'x+b'+26(Ax+B)

or 26(Ax+B)=0(26)

donc ax+b=a'x+b'(26)

donc si (a;b)=(a';b')(26) alors les codes sont les mêmes.

2c

le nombre de couples (a;b) différents si a=1..25 et b=0..25

est de 25*26

(il y a 25 possib pour a et 26 possib pour b; c'est combinatoire)

2d

avec la clé (2;13) on n'obtient pas tous les nombres entre 0 et 25.

(tu verras plus tard pourquoi, si tu veux vraiment savoir, je t'expliquerai)

B

c'est un peu plus compliqué.

on connait y, on cherche x.

attention ici car c'est une équation modulo (les solutions sont entières)!

7x+17=y(26)

regardons un peu...

on veut résoudre 7x+17=1(26)

soit 7x=1-17=-16(26) (pas de pb, passer 17 à droite, ça on peut faire)

par contre on ne peut pas diviser pas 7 pour trouver x!!!

il y a plusieurs méthodes ici.

en voici une:

7x=-16(26) se ramène à 7x=-16+26q soit

7x-26q=-16

(equation diophantienne en x et q)

en voici une autre(celle que l'on va faire dans ton devoir):

si on connait u tel que 7u=1(26)

(ce qui revient à : 7u=1+26v...)

alors c'est fini car:

7x=-16(26) donne 7ux=-16u(26)

donx x=-16u(26) (car 7u=1(26))

reste à trouver u puis on trouve alors x.

Allons-y!

B1a

chercher u,v tels que 7u-26v=1

regarde ton cours (sinon je t'expliquerai)

on trouve: u=-11-26k et v=-3-7k

(soit u=-11(26) et v=-3(7); bref)

7u-26v=1 donne 7u=1+26v soit 7u=1(26)

B1b

on a 7x+17=1(26) donc 7x=-16(26)

donc (on multiplie par u)

7ux=-16u(26)

or 7u=1(26)

donc

x=-16u(26)

B1c

on récapitule

x=-16u(26) et u=-11(26)

donc x=-16*-11(26)=176(26)=20(26)

c'est la lettre U.

(regarde mon tableau : vérifie que la lettre b(1) correspond à la lettre u(20) avec le codage 7x+17(26))

B2

rappel :

l'équation ax+by=c a des solutions ssi pgcd(a,B) divise c.

en particulier, si pgcd(a,B)=1 alors il y a tjs des solutions.

donc si a et b st 1ers entre eux.

dans notre cas:

ax+b=y(26)

soit encore ax-26q=y-b

on aura toujours des solutions si pgcd(a;26)=1

le décodage est donc assuré.

Voilà! :wink:

Si des choses coincent, n'hésite pas!

[philippe]

j'ai oublié le tableau!!!!!

:wink: