Maths spécialité TS (pgcd)

[Clarmaths]

Bonjour à tous,

Je sollicite votre aide car je bloque à un devoir maison de Spé maths (Je suis en terminale S).
Voici le Devoir en question :

[CENTER]Chiffrement Affine[/CENTER]

Le chiffrement affine est un procédé de cryptage par substitution à clé secrète qui consiste à remplacer chaque lettre par une autre lettre selon le principe décrit ci-dessous:
1. On choisit deux entiers a et b compris entre 0 et 25. Ces deux entiers constituent la clé secrète.
2. Pour " chiffrer " un message, on commence par l'écrire en supprimant les espaces et la ponctuation. On associe ensuite à chaque lettre un entier n selon le tableau suivant :

A 0
B 1
C 2
D 3
E 4
F 5
G 6
H 7
I 8
J 9
K 10
L 11
M 12
N 13
O 14
P 15
Q 16
R 17
S 18
T 19
U 20
V 21
W 22
X 23
Y 24
Z 25

3. On associe alors à n le reste f (n) de la division euclidienne de a×n+b par 26.
4. Enfin, on remplace f (n) par la lettre obtenue à l'aide du tableau précédent.

Cet algorithme fournit un procédé de chiffrement. Mais un bon système de chiffrement code deux lettres distinctes de façon différente. En effet, si deux lettres sont codées par une même lettre, il y aura un problème au moment du déchiffrement.


1. Montrer que l'algorithme décrit ci-dessus fournit un bon système de chiffrement si et seulement si a et 26 sont premiers entre eux.

2. En déduire les valeurs possibles de a et le nombre de clé secrète donnant un bon système de chiffrement.

3. On choisit dans cette question : a=17 et b=5 .
• Vérifier que la clé secrète permet d'obtenir un bon chiffrement.
• Chiffrer le message " SOLEIL ".

Mais je suis bloqué à la première question, car je déduis de l'énoncé que :

pgcd (a , 26) = 1

Et donc d'après le théorème de bezout, il existe (u;v) appartenant à Z² tels que :

ua + 26v = 1

J'ai aussi trouvé que pour qu'un chiffrement soit bon :

f(n) doit être différent de f(n') pour n'importe quels n et n' compris entre 0 et 25.

Mais je ne sais pas comment arriver à ce résultat. Des pistes ?

Merci d'avance.

[amine94]

Bonjour à tous,

Je sollicite votre aide car je bloque à un devoir maison de Spé maths (Je suis en terminale S).
Voici le Devoir en question :





Mais je suis bloqué à la première question, car je déduis de l'énoncé que :

pgcd (a , 26) = 1

Et donc d'après le théorème de bezout, il existe (u;v) appartenant à Z² tels que :

ua + 26v = 1

J'ai aussi trouvé que pour qu'un chiffrement soit bon :

f(n) doit être différent de f(n') pour n'importe quels n et n' compris entre 0 et 25.

Mais je ne sais pas comment arriver à ce résultat. Des pistes ?

Merci d'avance.

Bonjour,
essaye de poser ta deuxième supposition en équation et tu verras ou cela va te conduire

[Clarmaths]

Bonjour,
essaye de poser ta deuxième supposition en équation et tu verras ou cela va te conduire

Le théorème de bezout ou celle avec f(n) ?

[amine94]

Le théorème de bezout ou celle avec f(n) ?

les f(n)...

[amine94]

Quel est ton niveau d'études?

[ft73]

(C'est marqué dans le premier message...)

Quand on veut résoudre y=ax+b mod 26, on fait ax=y-b mod 26 et là on est embêté parce qu'on n'a pas d'inversion triviale dans Z.
Donc on cherche un entier, disons qu'on le nomme u :lol3: , qui soit un inverse de a modulo 26.
Une fois qu'on l'a, il vient uax=u(y-b) mod 26, etc.

[Clarmaths]

Je veux pas paraitre idiot, mais comment tu arrive à y = ax+b mod 26 ?

En fait, le problème avec cette question c'est que je ne sais même pas par où commencer ...

[ft73]

Je veux pas paraitre idiot, mais comment tu arrive à y = ax+b mod 26 ?

y=an+b mod 26, si tu veux. C'est ce qui est écrit comme codage dans ton énoncé.