spé maths cryptographie

A la liste des vingt-six lettres de l'alphabet rangées dans l'ordre habituel, on ajoute les signes suivants, dans cet ordre: [.] [,] ['] [?] [!] [ ]

le numéro 31).

a et b étant des entiers donnés, on définit l'application f de E dans E de la façon suivante: à tout élément de E de numéro x, f associe l'élément de E de numéro y, où y est le reste de la division euclidienne de ax+b par 32.
L'application f est appellée un codage affine.

1.a. Démontrer que, si a est premier avec 32, alors deux éléments distincts de E ont des images distinctes par f.

b. En déduire que f est alors une bijection de E dans E (cette condition est indispensable pour obtenir un "codage décodable").

voila le sujet de mon devoir de maths , or je suis totalement largée ... j'attends de l'aide merci d'avance....

Bonjour,
Suppose que deux éléments x et x' aient la même image : que peux-tu écrire ?

et bien si ces nombres son x et y je peux écrire que f(x)=f(y) ???

Appelle plutôt les deux nombres x et x', car y est déjà utilisé dans l'énoncé.

Détaille, et travaille modulo 32.

ah non je pense que f(x)=(ax+b)-32q
et que f(x')=(ax'+b)-32q'
or x=x'
⇔ax+b=ax'+b
mais après ?????

modulo 32 ....
je suis dsl mais là je ne vois pas du tout

Citation
or x=x'
⇔ax+b=ax'+bNon : on ignore si x et x' sont égaux.
Par contre, ils ont bien la même image, donc ax+b ≡ ax'+b modulo 32 car ce sont les restes qui sont égaux, mais pas forcément ax+b et ax'+b'.
Il en résulte que a(x-x') .....?

à moins que :
ax+b≡f(x)modulo32
ax'+b≡f(x')modulo32
soit a(x-x')≡f(x)-f(x')modulo32

Oui, mais tu tournes en rond : que vaut f(x) - f(x') ?

0 puisque les nombres ont la même image
don a(x-x') est divisible par 32

Exact, mais en plus on sait que a est premier avec 32, donc ?

donc x-x' est divisible par 32
mais ensuite je ne vois pas comment montrer que x=x'

Facile : x et x' sont tous deux dans E, donc x-x' est compris entre ... et ... ?

0≤x-x'≤31

non : -31 ≤ x-x' ≤ +31 car on ne sait pas si la différence est positive ou négative.
Mais c'est un détail, car il n'y a qu'un seul multiple de 32 entre -31 et +31 : c'est ?

0 ... donc x-x'=0
d'où x=x' ..... eureka

Voilà.
Je résume car je dois me déconnecter.
Si f(x) = f(x') alors x = x'
La contraposée : si x ≠ x' alors f(x) ≠ f(x') : deux éléments différents ont des images différentes : l'application est injective.

Pour la question 2 : c'est un théorème : toute application injective d'un ensemble dans lui-même est bijective.
Si tu ne connais pas ce théorème, raisonne sur le nombre d'images différentes à comparer avec le nombre d'images possibles.

A plus tard.
Si tu as besoin d'aide avant, sollicite un Modérateur par message privé.

le devoir se continue par un exemple de codage mais j'ai trouvé par contre la 3ème partie m'échappe totalement :
a) démontrer qu'il existe un couple (a;b) d'entiers compris entre 0 et 31, et un seul, qu'on déterminera, tel que f(K)=H et f(R)=C
b) c'est le décodage d'un texte qui serais a ma portée si je trouvais a et b

Je suppose qu'il s'agit des lettres de l'alphabet.
Les codes sont les suivants :
K : 10
H : 7
R : 17
C : 2
Donc on doit résoudre le système suivant :
10a + b ≡ 7 [32]
17a + b ≡ 2 [32]

En soustrayant, il vient : 7a ≡ -5 ≡ 27 [32]
Il faut ensuite pouvoir "diviser" par 7 ( afin de trouver a ).
C'est possible car 7 et 32 sont premiers entre eux :
il existe u et v tels que 7u + 32 v = 1 ( Bézout ).
Trouve une solution simple à cette équation.