congruences BAC S SPE 2018 Centres étrangers Ex4 le code RSA

Hans Amble - Maths au Lycée
10 abonnés
1 Vues de vidéo·31 oct. 2024
congruences BAC S SPE 2018 Centres étrangers Ex4 le code RSA
https://tiplanet.org/modules/archives/download.php?id=1563209
Alors bienvenue dans cette vidéo, je vous propose ici de corriger l'exercice 4 de SPE
du Bacchus 2018 Centre Étranger,
donc un exercice sur le fameux code RSA.
Alors ce code RSA, les lettres, on vous le rappelle,
c'est donc les initiales des 3 inventeurs,
3 mathématiciens.
Le sujet est divisé en 4 questions,
on vous dit d'ailleurs, ça c'est bien un coup découpé,
on vous dit que les questions 1 et 2
sont des questions préparatoires,
la question 3, on crypte,
c'est en haut à droite ici, on agrandira après,
et la question 4, on décrypte.
Donc on commence ici tout de suite
des petites égalités modulo 55,
donc ça, ça a l'air facile,
ça commence plutôt bien
parce que ça rassure tout de suite.
Donc des calculs, on est parti.
Je vais essayer de ne pas utiliser de machine,
on va voir si c'est possible dans le sujet,
et puis vraiment, si on n'y arrive pas,
on allumera une petite calculatrice.
Donc première question.
Alors, on vous demande de vérifier
que 8 puissance 7 est égale à 2 modulo 55.
Donc ça, c'est la question.
Alors, on va décomposer 8 puissance 7.
Alors, 8 puissance 7, qu'est-ce que c'est ?
C'est donc 8 au carré
fois 8 au carré
fois 8.
Ça a l'air un petit peu malheureux,
mais on va s'occuper de 8 au carré.
8 au carré, ça fait 64.
Et modulo 55,
64, c'est 55 plus 9,
donc 8 au carré,
c'est 9 modulo
55.
Donc, avec ça,
ça veut dire qu'ici,
8 puissance 7, qu'est-ce que ça va être ?
On a 8 au carré, 8 au carré, 8 au carré,
on a donc 9
fois 9
fois 8 modulo
55.
Ensuite, on continue dans cette idée,
on va faire 9 fois 9,
alors 9 fois 9,
ça fait 81.
Donc, 85,
qu'est-ce que c'est ? 55 plus 26.
Donc, ça vaut 26 modulo 55.
9 fois 8,
ça fait 72.
Et 55,
donc plus combien ?
Donc, on rajoute 10, c'est 7, on rajoute donc 17.
17, donc c'est 17
modulo 55.
Donc, on en est
à 8 puissance 7
est égal à 26
fois 17 modulo
55. Je vous montrerai d'autres méthodes,
vraiment, c'est pour faire un petit peu
de calculs sans machine, ça fait toujours du bien.
26 fois 17, vous pouvez le calculer.
Ça fait donc
26 fois 17, 6 fois 7,
42, plus 7, 14,
ça fait donc 18,
26, 22, 4,
442.
Alors, 442
modulo 55,
c'est combien ? Ce que vous pouvez faire,
là, peut-être, c'est utiliser
soit une division, vous regardez
combien de fois il y a 55, sinon vous faites une liste des multiples.
55, donc on a 110,
220,
330,
440. Ah, 440,
c'est un multiple, alors ici, on a
fois 2, fois 4,
fois 8.
Ça, c'est 8 fois 55
plus 2.
Donc,
effectivement, 8 puissance 7,
c'est donc 8 fois 55
plus 2, comme 55
vaut 0, donc 8 puissance 7 est égal à
2 modulo 55.
Donc voilà une première méthode, sans machine.
Il y a marqué
vérifier, donc voilà, j'ai bien vérifié.
Une autre méthode, c'est quand on arrive à
9 au cube, on le calcule, 9 au cube, ça fait
80 fois 9,
donc 9 fois 8, 72, 729,
et 729, et bien on va
faire une division par 55,
donc déjà, rapidement, on peut enlever
550.
Donc, si on fait 729
moins 550,
vous voyez, ici, donc,
9 moins 9,
donc là, c'est bon,
12 moins 5, 7,
il reste 179.
Donc, ça vaut
179 modulo
55. On peut encore enlever
3 fois 55, qui fait
165, donc il reste
14 modulo 55.
Donc ici,
eh bien, comme 9 au cube, c'est
14, ça fait 14 fois 8,
14 fois 8, 8 fois
80 et 132,
112, et 112, bien c'est
110 plus 2, donc ça fait 2 modulo
55. Voilà. D'accord ?
Alors après, on va rapidement regarder
la calculatrice, si on pouvait le faire.
Alors, 8 puissance 7,
c'est, donc,
2.097.152,
qu'est-ce qu'on peut faire ? Alors, il y a
plein de méthodes. La première, c'est
de faire la division Euclidienne à la main.
Avec la machine, mais en l'écrivant.
Pour ça, on divise tout simplement
par 55. On aura
le nombre entier, donc on aura
55 fois
38130. Par contre,
vous avez un reste. Comment trouver le reste ?
Eh bien, on fait, donc, le nombre de départ,
c'est-à-dire 8 puissance 7
moins 55 fois
38130.
Vous ne prenez que la partie entière.
Il vous reste 2, donc ça c'est
le reste. Ça fait, donc, ceci plus 2.
Ceci, c'est une division Euclidienne.
Donc, 8 puissance 7
va être égal à
2 modulo 55.
D'accord ? Puisque le modulo 55,
ici, tout ce terme-là, vaut
0. D'accord ?
Donc, d'une façon comme ça, rapidement,
si le nombre est calculable. Ici, il est de taille raisonnable.
Voilà. Ensuite, il y a une touche aussi
sur la calculatrice.
Pour la Casio 35, vous allez, donc,
dans le menu,
ici, numéro 1. Et là, vous allez appuyer
sur OPTN,
c'est-à-dire la touche OPTION.
Une fois que vous avez la touche OPTION, vous appuyez sur
ce petit triangle blanc, en haut à droite, au-dessus de la touche F6
pour obtenir un deuxième menu.
Ce deuxième menu,
ici,
je vais le faire en même temps que vous, vous allez dans NUM,
pour numérique.
Et une fois que vous êtes dans numérique,
vous appuyez une fois sur la touche NUM,
et là, vous allez trouver
une touche,
qui s'appelle MOD.
Donc, c'est cette touche ici
qui m'intéresse au plus haut point.
Donc, c'est la touche qui permet d'avoir le reste.
Modulo 55.
Donc, ici, on va taper MOD.
Quand vous tapez une parenthèse sous, vous écrivez 8 puissance 7.
Et là, vous mettez
virgule et le nom pour lequel
vous voulez faire la division. Donc, 55.
La calculatrice affiche 2.
Vous avez gagné. Voilà.
Ensuite, vous verrez, dans ce même menu, il y a une touche
ZGCD, qui fait le PGCD.
Donc, pareil, vous mettez des parenthèses, les nombres que vous voulez,
et ça vous donnera le PGCD. Donc, voilà pour les Casio.
Alors, sur une Texas,
on va donc dans Math, ici.
Math. Ensuite, on va
Nombre, le menu Nombre, et on va
il y a plein de choses, ici.
Et vous avez donc PPCM,
PGCD, ça c'est facile, et
REST. C'est lui qui m'intéresse.
8 puissance 7.
Quand c'est bien, on redescend.
Virgule 55.
On ferme la parenthèse.
Et on trouve 2. Voilà.
Ça, c'est donc la vérification.
Voilà. Alors,
ce que je vous propose comme réponse, c'est celle-là.
La division par 55, ça marche très bien.
Sinon, vous dites avec la touche Mode,
je trouve 2. Voilà. Vous n'êtes pas
obligé de passer, comme j'ai fait au début,
5 minutes à faire des petits calculs.
Sachez qu'il y en a qui vont faire directement
de petites questions. Ce qui est important, par contre,
et un conseil qui peut être précieux,
c'est qu'il faut toujours revire les questions avant d'aller à la
suivante. Et ici, effectivement, si vous regardez,
il y a des questions que je n'ai pas encore traitées.
On déduit le reste de la division qui vienne par 55
du nombre 8 puissance 21.
Comme c'est en déduire,
il faut faire le lien avec ce qu'on vient de faire. 21,
c'est 3 fois 7.
8 puissance 21,
c'est 8 puissance 7
fois 3. Et donc, par transformation,
c'est 8 puissance 7
au cube. Alors, rappelons
une formule très
importante. C'est que
si on a A qui est égale
à B modulo,
par exemple, M,
et si on prend un entier
strictement positif, eh bien A puissance
M sera égale à B puissance
M. D'accord ? Donc ici, on va l'utiliser
avec M ici égale
3 et M égale
55. Donc, qu'est-ce qu'on dit ?
Eh bien, 8 puissance
7 est égale à 2
modulo 55.
Donc, eh bien,
8 puissance 7
8 puissance
7 au cube
va donc être égale à 2 au cube
modulo
55. Par conséquent,
eh bien, ça veut dire que 8 puissance
7 au cube est donc égale à 2
au cube, c'est-à-dire 8 puissance 55.
Voilà. Alors, ça, c'est pas
encore exactement la réponse à la question.
Ça, ce n'est pas une division
euclidienne. Donc, pour un reste,
il faut une division euclidienne.
Une division euclidienne, c'est donc l'écriture
de votre nombre, 8 puissance 7
au cube, sous la forme P fois Q plus R,
avec ici R entre 0
et donc strictement
votre diviseur, c'est-à-dire 55.
Donc, je vais écrire quoi ?
Et d'après ça, donc, puisqu'on a
8 puissance 7 au cube égale à 8
modulo 55, donc,
il existe un nombre Q
appartenant à Z tel que
8 puissance 7 au cube,
eh bien, ça s'écrit
donc 55
fois Q plus 8.
C'est la définition des
modulos 55. Or,
qu'est-ce qu'on remarque ?
Votre nombre 8, il est bien entre 0 et
55.
Donc, cette écriture
est la division
euclidienne, c'est ce qu'on appelle la division
euclidienne
de 8
puissance 21
par 55.
Le reste
est donc
votre nombre 8.
Donc voilà, c'est ce qui est important
surtout pour les révisions pour le bac,
définition que je vous rappelle de la division
euclidienne. Quand on divise N par
P, eh bien,
il doit y avoir ici un reste
qui est entre 0,
j'ai mis un 0 ici,
c'est un 0 inférieur. Attention, très très
important, cette
petite remarque là dans l'exercice,
ça ne joue pas, mais ici le reste peut être
nul, évidemment. Je pense que vous l'aviez
vu. Si le reste est nul,
c'est tout simplement que P divise N.
C'est important que le reste puisse être nul.
Par contre, si vous trouvez une écriture
ici avec un nombre qui est plus grand que le diviseur,
ce n'est pas une division euclidienne. Ce n'est pas forcément
faux, mais ce n'est pas la division euclidienne.
La division euclidienne d'un nombre par un autre,
c'est cette écriture spécifique
ici avec un nombre
qui est strictement plus petit
que le diviseur et supérieur ou égal à 0.
Voilà, on se croit avoir
bien rectifié, donc très très important.
Vous voyez une petite question, déjà, pleine d'enseignements.
Donc, on continue.
Pour l'instant, un sujet qui me plaît
plutôt, parce qu'on révise beaucoup
de petites notions. Question B.
Alors, vérifier
que 8² égale 9 modulo 55.
Alors, je l'ai fait tout à l'heure, on va le refaire, parce que certains n'ont pas
tout regardé. 8²
c'est donc 8 fois 64.
J'avais dit que c'était
55 plus 9,
donc 8²
égale à 9 modulo
55. D'accord ?
Et maintenant, on doit déduire la question précédente, le reste de
la division de 8
puissance 23 par 55. Alors, qu'est-ce qu'on fait ?
8 puissance 23,
vous savez, c'est, si on veut
revenir aux questions d'avant, on va essayer de se ramener à 8 puissance
21, c'est 8 puissance 21
fois 8².
D'accord ?
Donc là, je rappelle une petite
propriété aussi sur les congruences.
Donc, si A et B sont égaux
modulo M et C et D sont
égaux modulo M, alors, il y a A
plus C est congruent à B plus D et A
fois C est congruent à B fois D. Voilà.
Donc, c'est très simple. Ici, qu'est-ce qu'on va faire ?
Je vais la décomposer, vous avez bien compris.
8 puissance 21,
qu'est-ce qu'on a dit ? Ça faisait 8.
D'accord ? Et 8², on vient
de dire que ça fait 9.
D'accord ? Donc, quand on
fait le produit, on peut faire le produit.
8 puissance 23 est donc égale à
8 fois 9 modulo
55. Alors, 8 fois 9,
ça fait 72.
Or, 72,
c'est quoi ? C'est 55 plus
17.
Et bien donc, 8 puissance
23 est
égale à
17 modulo 55.
Donc, toujours, une réponse,
on doit donner le reste du division Euclidienne.
Donc, on va écrire le division Euclidienne et bien dire que
ce reste est entre 0 et
55, exactement.
Alors, soit ça, vous l'écrivez bien avec
l'histoire de il existe cas, sinon vous dites,
Or, 17 est bien
entre 55
et 0, mais strict en 55.
Donc, le reste
de la
division
de 8 puissance 23
par 55
est donc
17. Voilà, pour cette
première petite partie
plutôt calculatoire, mais qui m'a
permis de vous faire quelques rappels qui sont quand même
importants. Deuxième question,
donc ici, on considère une équation
Diophantienne, donc l'équation
E, sur un format x plus
py égale 1, qui est 23
x moins
40 y égale 1.
Voilà, et on cherche
donc des solutions
qui sont x et y,
donc des couples d'anti-relatifs qui s'appartiennent
à z. Donc, c'est des
couples z, donc ici, on est par notation
z2, mais attention, ce n'est pas des carrés, c'est juste
des couples où le premier x
appartient à z et le y aussi.
Voilà, c'est juste précision.
Donc maintenant, première chose,
alors on est sur du grand, grand classique,
ça c'est du cours, il faut faire ça, il faut que ça déroule.
Justifiez le fait que l'équation E
admet au moins un couple solution.
Alors là, où vous avez dormi toute l'année,
où vous savez,
et donc ici, qu'est-ce qu'on dit ?
Eh bien, 23
et 40 sont premiers entre eux.
D'accord ? Donc, à
le terrain, c'est après le terrain de Bézout.
Donc, d'après
le théorème de
monsieur Bézout,
qu'est-ce qu'on dit ?
Il existe un couple
uv,
relative,
tel que
au plus bv
est égal à 1. D'accord ?
Ça c'est le terme de Bézout.
Il y a deux versions, vous avez au plus bv
est égal à 1, à condition de mettre ici
un moins,
vous aurez ici un autre antératif,
il faudra mettre moins v. Donc ici, vous pouvez très bien écrire
Bézout sous la forme
d'une soustraction, ça ne pose pas de problème,
c'est exactement l'intérêt.
Donc, s'il existe un couple uv avec au plus bv
égal à 1, il en existera un avec au moins bv.
Donc, ne vous inquiétez pas, eh bien,
ce couple
uv est solution
de E.
Alors évidemment, là j'ai mis
au plus bv,
quand vous allez le rédiger,
vous n'allez pas mettre au plus bv,
vous allez mettre, vous,
23u-40v.
Vous voyez bien,
on reconnait presque l'équation,
mais à la place de x et y, il y a u et v, donc ce couple uv
c'est ce couple qui est solution de E.
Donc, il existe au moins,
vous pouvez dire,
il existe au moins
un couple
solution.
Et d'après le fait,
l'information importante,
c'est que 23u-40v sont premiers entre eux.
Alors, est-ce que ça justifie ? Non.
23u-40v sont premiers,
donc pas de problème,
vous voyez que 40u-40v n'est pas divisible par 23u-40v,
donc 23u-40v sont forcément premiers entre eux.
Alors, ceux qui veulent tout justifier,
vous avez tout à fait le droit,
et d'ailleurs vaut mieux trop justifier que pas assez,
comment pourrait-on faire ?
Alors, soit vous dites,
23u-40v est premier,
40u-40v c'est quoi ? C'est 5u-8u,
donc c'est 5u-2u,
donc vous voyez qu'il n'y a pas de diviseur ici commun.
Ou alors,
l'algorithme d'Euclide, vous faites 40u-40v égale
23u-40v x 1u-40v
plus 17u-40v,
23u-40v est donc égal à 17u-40v x 1u-40v
plus 6u-40v,
on repart de 17u-40v à 17u-40v,
c'est quoi ? 6u-40v x 2u-40v, 12u-40v
plus 5u-40v,
et après on y est presque, 6u-40v x 2u-40v
égale 5u-40v plus 1u-40v,
à un moment on est arrivé à 1u-40v,
donc 40 et 23 sont premiers.
Bon, sincèrement, pour des nombres comme ça,
en dessous de 100, on peut très bien admettre
que vous savez que les deux nombres
sont premiers entre eux. Donc voilà la première question.
Maintenant justement, vous avez montré
qu'il existait au moins un couple, et on va en donner un.
D'accord ? C'est pour ça que dans la première question,
il ne s'agit pas de trouver un couple,
il s'agit vraiment d'utiliser le théorème de Bézout.
Vous avez normalement fait ça
plein de fois dans l'année.
Donc comment on fait pour trouver un couple ? Alors là,
il y a vraiment plein de méthodes.
Je ne sais pas exactement ce que le
corrigé attend, vraiment.
Il y a marqué données. Alors à partir du moment où il y a marqué données,
vous pouvez très bien donner direct.
Alors 23u-40v, ce n'est pas si simple,
il n'y a pas comme ça une solution qui m'apparaît
évidente. Parce que 23u-40v
donc vous pouvez regarder les multiples,
il y a une solution qui consiste à écrire les multiples,
23u-40v, 46u-40v, puis vous regardez
si vous êtes tout près de 40, ou d'un multiple.
Donc ça fait 69u-40v,
là ce n'est pas bon.
69u-40v après, donc 23u-40v
93u-40v, 94u-40v, 92u-40v,
jusque là, on n'est pas bon.
On n'est pas prêt d'arriver.
Donc là, à la main, ce n'est pas si simple.
Donc, deuxième méthode, à la
calculatrice. Alors pour ça,
vous avez donc dans le menu
table, on va faire un tableau de valeur.
Alors pour quelle fonction ? C'est très simple.
Je vais l'avoir fait une fois. Ici je vais
isoler y à gauche. Donc je vais mettre
40u-40y
égale 1-23x
ça veut dire que y, ça doit être
égal à 1-23x sur
moins 40. Donc je vais
rentrer cette fonction là.
C'est donc la fonction 1-23x
1-23x
divisé par
moins 40. Voilà.
Et je vais faire un tableau, mais avec
que des nombres entiers. Donc je vais partir
par exemple à moins 20,
et j'irai jusqu'à, je ne sais pas, moins 50, on verra bien.
Et on va surtout de 1 en 1.
On va tester toutes les valeurs entières de x.
On va voir quand est-ce qu'on trouve
ici un y entier.
Donc tableau, et je regarde.
On fait comme ça la colonne de droite, on regarde quand est-ce qu'on a un nombre
entier.
On sait qu'il y en aura, d'accord ?
Et à un moment ça va passer, donc soyez patient.
Ah, c'est bon, 7. Donc ici,
pour x égale 7, y vaut 4.
Donc ici, pour
x égale 7,
y est égal à 4. Donc,
le couple 7-4
est solution.
D'accord, on va quand même le vérifier.
Voilà, donc j'arrive à la machine,
regardez, alors 23
x 7, ça fait combien
ça ? 23 x 7,
20 x 7, 140, ça fait ça
161.
Ensuite, moins 40
x 4, ah oui, moins 160,
ça fait bien 1. On vient de trouver un couple solution, vous voyez,
à la machine. Ça c'est méthode, on va dire,
numéro 2. Méthode numéro 1,
c'est on cherche comme ça au hasard, on trouve ou pas.
Méthode numéro 2, à la calculatrice.
Méthode numéro 3, l'algorithme d'Euclide.
J'essaie vraiment de faire un max parce que
le bac arrive et donc ça fait une bonne révision,
tout ça. Alors l'algorithme d'Euclide,
tout à l'heure je l'ai fait, je vais le refaire,
on a dit 40, c'est 23 x 1
plus 17.
Ensuite, on prend 23 et on divise
par 17. 23 x
17 x 1 plus 6,
ensuite 17 égale
6 x 2, 12
plus 5,
après 6 égale 5
x 1 plus 1.
Et là donc on va se servir de 1. Ce 1 en fait,
ça va être le 1 de l'équation,
le 1 qui est à droite. Donc déjà, on va
remonter ce qu'on appelle l'algorithme d'Euclide.
Ici on écrit 6 moins 5
égale à 1. Vous voyez, j'ai mis le 5
à gauche. Après je vais
enlever ce 5, je vais le substituer
par la valeur que me donne l'équation
d'égalité juste du dessus.
L'équation c'est l'égalité,
donc ça fait 6 moins
17 moins 6 x 2.
Et là on regroupe.
Alors dès 6, j'en ai
un là, et ensuite en développant, j'aurai 6
moins 17 plus 2 x 6, donc
j'ai 6, j'en ai 6 x 3
moins 17 égale à
on vérifie, ça fait bien 18 moins 17 égales
et on continue. Maintenant, étape suivante,
je substitue ce 6
ici, ce 6 là
par ce que je vais trouver là.
Alors d'après la ligne ici,
26 et 23 moins 17, donc là j'écris
23 moins 17
je compte. Combien y a-t-il de 17 ?
Alors dès 23, pardon,
23 x 3, donc ça c'est bon. Dès 17
j'en ai moins 3 moins 1, donc
4 x 17.
On peut vérifier. 23 x 3
donc ça fait 92
pardon, 23 x 3
ça fait, je dis des bêtises, pas du tout
ça fait 69, 69
moins 68, ça fait bien 1.
On continue. Toujours un petit peu long.
Cette fois-ci ce 17,
on va le substituer par ce que ça nous donne
en première ligne.
J'obtiens, toujours un petit peu long,
23 x 3 moins
40 moins 23 x 4
égale à, je regroupe
dès 23, j'en ai 3 ici,
ensuite, attention, moins par moins
plus 4, donc 23 x
7 moins 40
x 4 égale à
le couple. Je l'ai.
On reconnait l'équation
dans laquelle j'ai remplacé x par 7
et y par 4, donc ici
x égale à 7, y égale à 4
donc on retrouve bien, vous voyez, quelle que soit
la méthode. Bon, alors le verbe
du sujet, c'est
donner, donc effectivement, je crois
qu'on peut se contenter de prendre la machine et
de dire, grâce à la machine
j'ai trouvé ça, alors vous pouvez indiquer votre méthode en disant
que vous avez fait un tableau de valeur de telle fonction
et que vous avez trouvé ce coup. Maintenant
la question c'est, c'est la résolution
d'une équation du offre ancienne, donc ça
normalement ça a été travaillé au cours de l'année, donc
deux choses, on va utiliser
Gauss et on va faire une réciproque
donc très importante.
Première étape, dans la résolution d'une équation
du offre ancienne, tout d'abord
on réécrit l'équation
et on prend, donc on écrit toujours
soit x, y un couple solution
soit x, y solution. Dans ce cas là
on a 23x
moins 40y qui est égal à 1
ensuite on sait que 23
fois 7 moins 40
fois 4 est égal à 1
on fait la différence
on obtient donc
que 23 fois
x moins 7
ici, moins 40 fois
y moins 4 est égal à 0
donc
23 fois x moins 7
est égal à 40 fois
y moins 4. D'accord, ça c'est la
première étape, on va
appliquer tout de suite le terme de Gauss
en disant quoi, bien 23
vous voyez, divise le côté droit
43y moins 4
et qu'est ce qu'on sait, bien 23
et premier, pas 24
c'est 23 et
premier avec 40
donc on écrit 23, le petit symbole
sinon vous écrivez en français
23 et 40 sont premiers entre eux
et donc là, petite accolade
théorème, le théorème
de Gauss, 23
divise donc
y moins 4
et donc, et là c'est important
il existe un antiréactif
z, e, k
tel que y moins 4
s'écrit 23 fois k
donc très important à ce moment là
que vous compreniez bien tout
c'est qu'ici, il existe
un antiréactif, c'est pas pour tout cas
donc il existe, on raisonne
par implication et notre point de départ c'est
si x et y sont solutions, dans ce cas là
vous en déduisez que y s'écrit
d'une façon particulière
dans ce cas là, y s'écrit 4
plus 23, donc si x et y
sont solutions, vous pourrez trouver un nombre
4 tel que y s'écrit 4
plus 23, ensuite
l'étape suivante, c'est pareil, il y en a
parfois qui se trompent, cette
chose là, on va la remettre
dans l'équation ici
d'accord, donc si vous remettez ça
là dedans, donc
il y a 23 fois
x moins 7, va être égal
à quoi, à 40 fois
et là on ne remet pas y moins 4, à la place
on met 23 fois k
ce qui fait que vous avez trouvé x en fonction de k
le même k que pour y
ici on simplifie par 23
ça veut dire que x moins 7
égale 40k, et donc
x égale 7 plus
40k, on voit première étape
donc si un couple x et y
est solution, vous pourrez trouver une écriture
de x et de y avec ici
l'existence d'un nombre k
et maintenant qu'est-ce qu'on va faire
et bien on va essayer de faire la réciproque
c'est à dire montrer que tous les couples qui s'écrit comme ça
vont être solution de l'équation
et donc on aura terminé
maintenant donc cette réciproque
c'est quoi, il faut montrer que quel que soit
maintenant k, et bien ce couple
7 plus 40k, 4 plus 23k est solution
donc qu'est-ce qu'on fait, on remplace dans l'équation
ce n'est qu'une simple formalité
23 fois 7 plus 40k
moins 40 fois
4 plus
23k est égal
à quoi, 23 fois 7
plus 23 fois
40k, je ne calcule surtout pas
moins 40 fois 4
moins 40 fois
23k, alors combien ça fait déjà, ça s'aligne
avec ça, il vous reste quoi
23 fois 7
moins 40 fois 4, ça en a déjà eu plusieurs fois
parce que 7x4 est solution
d'équation E, ça, ça fait 0
qu'est-ce qu'on vient montrer, et bien donc
l'ensemble solution
de E
c'est l'ensemble des couples
et là j'ouvre des accolades
puisque je fais l'ensemble de tous les couples qui s'écrivent
7 plus 40k
4 plus
23k
et k appartenant à z
quel que soit donc k, on est passé
vous voyez dans cette réciproque
je vais l'entourer ça en jaune, de
il existe k à
pour tout k, donc on a généralisé
et ça c'est très important
donc obligatoirement dans votre raisonnement il va y avoir
la première étape avec le terme de Gausset
il existe et ensuite la généralisation
qui transforme lui existe dans quel que soit
donc très très important
on a donc fait la question C
en déduire qu'il existe un unique
entier d vérifiant donc d entre 0 et 40
et 23d égale 1 modulo 40
donc déjà
23d
est égal à 1 modulo 40
ça équivaut à quoi ?
ça veut dire qu'il existe un nombre k
appartenant à z tel que
23d
est égal à 1
il n'y a plus la conférence
est égal à 1 plus 40k
donc ça veut dire
que 23d
moins 40k est égal à 1
conséquence, alors j'ai mis k
c'était peut être pas très heureux
donc je vais mettre ici un grand k
pour ne pas mélanger avec le k qu'on a déjà dans la question d'avant
voilà, qu'est ce qu'on a ici ?
ça veut dire donc
vous voyez ça, ça ressemble à l'équation
ça veut dire que le couple
donc le couple
ici d grand k
est solution
de E
puisque 23d moins 40k est égal à 1
conséquence, on connait
les écritures de tous les couples
donc forcément
il existe un petit nombre k justement
appartenant à z tel que
d s'écrive 7 plus
40k et d'ailleurs
on ne s'en servira pas mais grand k ça sera
4 plus 23 petit k
donc d est égal à 7 plus 40k
alors nous
on veut quoi ?
on veut d entre 0 et 40, donc on va résoudre
donc on va poser
d comme ceci
et on va transformer cet encadrement
ça veut dire qu'on cherche
petit k tel que
7 plus
40k
entre 0 et 40
on enlève 7 partout, ça fait
moins 7, 40k
donc 40 moins 7
33, je divise tout par 40
qui est positif, donc
k est entre 33 sur 40
et il est supérieur
à moins 7 sur 40
conclusion, vous cherchez un nombre entier
comme il est entier
il doit être strictement plus petit que 33
quart, d'accord ?
33 quart c'est 0,9
donc k est strictement plus petit que 1
et il est super égal à
ici, alors là vous voyez
ça c'est moins 1
donc forcément il est
supérieur ou égal
uniquement à 0, il est strictement plus grand
que moins 1, donc quelle est
la possibilité ? La seule possibilité
c'est k égale 0
k égale 0 ça vous donne donc
d égale 7
et effectivement, 7
entre 0 et 40
23 fois 7 égale à 1 modulo 40
ça on l'a déjà vu, c'est notre solution
donc, on a unicité
parce que j'ai toutes les conditions
et la seule possibilité à la fin c'est d égale 7
il existe une unique
possibilité
c'est donc d égale 7
maintenant on passe à la troisième question
cryptage dans le système RSA
donc une personne a choisi deux noms premiers
p et q
et calcule le produit
donc n, donc p fois q
et p moins 1 fois q moins 1
vous voyez dans la question 1, on nous demandera
de calculer N et N pour
deux valeurs précises de p et q qui sont 5
ensuite, elle choisit également
un entier naturel C premier avec N
le couple N
N C, c'est ce qu'on appelle une clé publique
tout le monde le connait
et les messages sont numérisés et transformés
le texte est un petit peu long
mais bon, on a une suite d'entiers compris entre 0 et
N moins 1
pour crypter, on procède ainsi
on calcule le reste
dans la division qu'il y a par N
du nombre A puissance C
et le nombre crypté
est l'entier B
dans la pratique, cette méthode
est sûre, si la personne A choisit le nombre
premier, très grand évidemment
nous on va prendre des petits parce que sinon les calculs
sont infaisables à cause des puissances
donc on prend quoi, je vais faire ça à droite
on va tout faire avec les exemples
p égale 5
q égale 11 et on a dit qu'il fallait qu'elle choisisse
un nombre premier
avec N, alors N c'est quoi ?
ici c'est la question A
il faut calculer N
donc N c'est
p fois q, c'est donc 5 fois
11, donc 55
ah, on a déjà vu ce nombre là dans les premières questions
N
c'est donc p moins 1, q moins 1
ce qui fait 4 fois 10
40, ah, 40 ça nous dit
quelque chose, on avait dans notre équation du haut foncière
on avait un 40
justifiez que la valeur de C vérifie la condition
voulue, alors C
sa seule condition, c'est un entier naturel
d'accord, donc
elle a pris 23
23 c'est bien
un entier naturel, et est-ce qu'il est premier avec
40, effectivement 23
et 40 sont premiers
donc 23 et 40 sont premiers entre eux
ça ça a déjà été démontré, donc
C vérifie
la condition voulue
les deux conditions, entier naturel
et premier avec
petit n, voilà on a fait déjà une question
vous voyez là ça reste abordable
maintenant
on veut envoyer à personne A
le nombre a, a égale 8
on va donc regarder
quelle phrase nous intéresse, pour crypter un entier
A, on procède ainsi, on calcule
le reste B dans la division
euclidienne par n du nom A puissance C
donc qu'est-ce qu'il faut faire
on calcule
donc il faut
trouver, ou calculer
le reste
de la division
de qui, donc
de A puissance C
donc ici de 8 puissance
C, donc 8 puissance
23
par, donc
on a dit, grand n
qui vaut 55, ah super
puisque là on se dit c'est cool, on l'a déjà fait
c'est encore écrit en haut
je l'avais gardé, c'était la question
du début, or
on a déjà répondu, or
on sait, c'était la question du début
que ce reste
vaut 17
déjà fait, je vous rappelle
le numéro de la question
c'était la question, donc 1
B, entre parenthèses, on peut mettre
question 1 B
et donc la valeur de B
c'est donc 17
c'est une question qui est très rapide
tout a déjà été fait, donc c'est juste une question
de lecture attentionnée du texte
dernière question
décryptage, donc la personne calculant
dans un premier temps l'unique quantité naturelle d
vérifiant d entre 0 n
et c d égale à 1 mod n, ça me rappelle la question
2 ça, elle garde ce nombre d
secret, tout à l'heure je crois
qu'on avait trouvé 7, donc on va
certainement retrouver ça, pour décrypter
la personne calcule, donc le reste
dans la division qui vient par
grand n du nombre B puissance d
et le nombre en clair
et le nombre petit a, d'accord
donc les nombres choisis c'est 5
11 et 23, ça n'a pas changé, quelle est la valeur
de d, alors qu'est ce qu'on veut
on va réécrire, on veut
donc d entre
0 et petit n, donc petit n
c'est 40, et c d
alors c d, c ça fait quoi
23 d
est égal à 1 modulo 40
alors ça d'après la question
cette question rappelée
c'est la dernière question de la partie 2
donc 2 d, on sait que
on sait que d est
égal à 7
voilà, déjà fini, vous voyez
ça c'est très rapide ces questions 3 et 4
le début était pas
inintéressant, là c'est presque trop simple
en appliquant la règle de décryptage
vous retrouvez le nombre en clair
lorsque le nombre crypté est 17, donc
comment on fait, il nous faut quoi
on doit calculer, donc ici j'écris
on doit calculer
le reste, donc de la
division, alors on le précise
je ne dis pas qu'il y en a, la division qui vient donc
de B puissance d
alors B, combien vaut B
B égale 17
d'accord, puissance
donc puissance d
donc 17 puissance 7
par, là on nous dit
par N, donc par 55
alors on a déjà fait ça
plein de fois, donc qu'est ce qu'on peut faire
on peut soit faire un gros calcul directement
sinon 17 au carré
vous savez que ça fait 289
normalement, c'est des carrés qu'on doit connaître
après on va faire, on va regarder par rapport à
55, donc 55 on a dit qu'il y avait
220, ça c'est
4 fois 55, et donc
260, on rajoute 55
275, donc il reste
14, ça veut dire que 17 au carré
c'est 14 modulo
55, donc on a la puissance 7
donc 17
puissance 7, qu'est ce que c'est
c'est 17 au carré fois 17 au carré
fois 17 au carré fois 17
donc 14 fois 14
fois 14 fois 17
et ça un modulo
55, on continue tranquillement
alors 14 fois 14, je vais le faire
là, 14 au carré
vous connaissez normalement, c'est 196
et 196
alors on est pas très loin
de 220 on va dire, c'est pas mal
donc ça fait moins 24
donc moi j'ai pris moins 24
et ensuite on a 14 fois 17
alors 14 fois 17 ça je le connais
pas par coeur, donc on fait
la multiplication, 4 fois 7
28, il reste 2, 9
14, donc
238, on est donc
pas loin de 220, ça fait 18
fois 18, modulo
55, alors 24
fois 18
je sais vraiment diviser la machine
fois 16, 19
4, 2, 3
donc ça fait ici
432
alors là
modulo 55, qu'est ce qu'on avait
on avait dit 110
220, 330
440, donc on est
juste à, on est à 8
donc ça fait moins 8, donc ça ça fait
8, modulo
55, donc réponse
qu'est ce qu'on vous dit, on veut donc
un reste de division qui vienne, or 8
et bien entre strictement plus
que 55 est positif, donc
le nombre
et bien le nombre ici
de départ, c'est à dire ici on cherche
le nombre petit a
c'est donc égal à 8, voilà
l'exercice est terminé, alors pour finir
donc, bilan, dans la question 3 on avait
crypté le nombre 8 et ça donnait 17
et là vous voyez qu'en décryptant le nombre 17
on retrouve 8, donc voilà
la boucle est bouclée, cet exercice est
terminé, je vous souhaite une bonne fin de journée à tous
et des bonnes révisions, bon courage
