Ceci est une ancienne révision du document !
Warning: Undefined array key 1 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 172
Warning: Undefined array key 1 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 172
Warning: Undefined array key 1 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 172
Warning: Undefined array key 1 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 172
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Table des matières
Modulo et chiffrement
Rappel de ce qu'est modulo
Le modulo suit le principe des points d'une horloge. Prenons les points sur le cercle à droite. Nous avons 12 points sur le cercle, il s'agit donc d'un $\mod 12$.
L'idée est de compter les points dans le sens indiqué et si on dépasse 11, de continuer en boucle. À ce jeu, on réalisera que le nombre 53 tombera en face de 5.
$$53 = 4 \times 12 + 5 \Rightarrow 53 \mod 12 = 5$
5 est donc le reste de la division entière de 53 par 12 ce qui s'écrit en Python :
>>> 53 % 12 5
53 est donc au même endroit que 5 sur notre cercle. Le mathématicien, rigoureux, ne dira pas que 53 est égal à 5. Il dira que ces deux nombres sont équivalents d'un certain point de vue et il pourra l'écrire de cette façon $53 \equiv 5 \, [12]$.
Multiplications modulo
Le modulo a une propriété intéressante que nous allons voir sur un exemple :
- $(17 \times 23) \mod 7 = 391 \mod 7 = 6$
- $(17 \mod 7) \times (23 \mod 7) = 3 \times 2 = 6$
>>> 17 * 23 % 7 6 >>> (17 % 7) * (23 % 7) 6
Voici un autre exemple. Supposons que l'on veuille calculer :
$$(45 \times 17 \times 22 \times 16 \times 29 \times 89 \times 12) \mod 7$$
>>> 45 * 17 * 22 * 16 * 29 * 89 * 12 8340140160 >>> 8340140160 % 7 2
Calculer la multiplication d'abord puis le modulo fait passer par un grand nombre intermédiaire. Voici ce que l'on aurait intérêt à faire (en décomposant – à droite)
>>> 45 % 7 3 >>> 3 * 17 51 >>> 51 % 7 2 >>> 2 * 22 44 >>> 44 % 7 2 >>> 2 * 16 32 >>> 32 % 7 4 >>> 4 * 29 116 >>> 116 % 7 4 >>> 4 * 89 356 >>> 356 % 7 6 >>> 6 * 12 72 >>> 72 % 7 2
Le résultat est le même et si je vous le mets en avant, c'est parce que ce n'est pas un hasard : C'est toujours le cas. On peut multiplier d'abord puis faire modulo, ou faire modulo d'abord puis multiplier (et éventuellement refaire modulo)
