Table des matières
Exponentiation modulaire
Dans un premier temps, on souhaite faire le calcul $a^b$, avec $a$ et $b$ entiers positifs, le plus rapidement possible. Mais ce qui nous intéresse vraiment, c'est le caclul $a^b \mod p$ car c'est un calcul très utilisé en cryptographie.
On serait tenté d'utiliser l'opérateur de puissance **, mais dans le cas avec modulo, c'est une mauvaise solution comme nous allons le voir.
Je fais plus loin un bref rappel de ce qu'est un modulo. Vous pouvez aussi lire chiffrement_modulo.
D'abord sans modulo
Méthode naïve
Supposons que je veuille calculer $3^{100}$ en n'utilisant que des multiplications. On revient à la définition de la puissance :$3^{100} = \overbrace{3\times 3 \times \cdots \times 3}^{100\times}$.
On pourrait donc faire les 100 multiplications.
En général, $a^b = \overbrace{a\times a \times \cdots \times a}^{b\times}$ ce qui donne :
ENTRÉES a et b, entiers positifs
SORTIE a^b
DÉBUT
soit r = 1
RÉPÉTER b FOIS
r prend la valeur r * a
FIN
RENVOYER r
FIN
À faire : écrire la fonction Python exponentiation_naive(a, b) implémentant cet algorithme.
Vérifiez que :
assert exponentiation_naive(3,100) == 3**100
Méthode rapide
Certains calculs peuvent aller plus vite : Par exemple, $3^{16} = \left(\left(\left(3^2\right)^2\right)^2\right)^2$.
- $3^2 = 3 \times 3 = 9$
- $9^2 = 9 \times 9 = 81$
- $81^2 = 81 \times 81 = 6\,561$
- $6\,561^2 = 6\,561 \times 6\,561 = 43\,046\,721$
Cette astuce ne fonctionne que pour un exposant puissance de 2. Mais on s'en sort très bien dans les autres cas.
$$3^{100} = 3^{64} \times 3^{32} \times 3^4$$
En suivant ce guide on constate qu'il suffit de faire 6 calculs $()^2$ et 3 multiplications pour obtenir le résultat de $3^{100}$. C'est plus rapide que de faire 100 multiplications comme dans la méthode naïve.
La décomposition $100 = 64 + 32 + 4$ correspond à une décomposition binaire : $100 = 1100100_2$. On reconnaît donc dans l'algorithme suivant une méthode de division successives.
ENTRÉES a et b, entiers positifs
SORTIE a^b
DÉBUT
r prend la valeur 1
p prend la valeur a
TANT QUE b > 0 RÉPÉTER
SI b mod 2 = 1 ALORS
r prend la valeur r * p
FIN
p prend la valeur p * p
b prend la valeur b // 2
FIN
RENVOYER r
FIN
Les calculs que l'on fait ici produisent des entiers très grands qui dépassent largement la capacité des entiers ordinaires : les entiers de Python, comme dans de nombreux langages, occupent 4 octets en mémoire et doivent pouvoir contenir aussi des entiers négatifs. Donc la valeur maximale est d'à peu près $\frac{2^{4\times 8}}{2} \approx 2\cdot 10^9$. Mais avec les grands entiers, Python passe automatiquement dans un mode spécial permettant des entiers de taille arbitraire, aussi grands que l'on veut, en tenant compte de la capacité mémoire de la machine. Les calculs deviennent plus longs à exécuter.
À faire : Écrire la fonction exponentiation_rapide(a, b)
Vérifiez que :
assert exponentiation_rapide(3,100) == 3**100
Exponentiation modulaire
On souhaite calculer $a^b \mod p$. La cryptographie fait grand usage de ce calcul.
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]$ ou encore $53 \overset{12}{\equiv} 5$.
Multiplications modulo
Le modulo a une propriété intéressante : on peut le distribuer sur l'addition et la multiplication. Voyons 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)
>>> 45 % 7, 17 % 7, 22 % 7, 16 % 7, 29 % 7, 89 % 7, 12 % 7 (3, 3, 1, 2, 1, 5, 5) >>> 3 * 3 % 7 2 >>> 2 * 1 % 7 2 >>> 2 * 2 % 7 4 >>> 4 * 1 % 7 4 >>> 4 * 5 % 7 6 >>> 6 * 5 % 7 2
- Ne croyez pas que décomposer est plus long pour la machine : la machine ne sait de toutes façons pas calculer
45 * 17 * 22 * 16 * 29 * 89 * 12, elle fait le calcul par étape. - En appliquant modulo progressivement, on n'a jamais de trop grand nombre. C'est important car en cryptographie, on utilise de très grand nombre et on ne veut pas que des calculs intermédiaires fassent apparaître des nombres encore plus grands.
Application à l'exponentiation
Supposons que je veuille calculer $3^{100} \mod 43$. Je peux faire le calcul de deux façons :
- Calculer d'abord $3^{100}$ (gros calcul) puis calculer le modulo 43.
>>> 3**100 515377520732011331036461129765621272702107522001 >>> 515377520732011331036461129765621272702107522001 % 43 23
- Calculer $3^{100}$ progressivement en appliquant modulo 43 chaque fois qu'un résultat intermédiaire dépasse 43. Ce faisant, aucun calcul intermédiaire ne concerne de grands nombres.
La première méthode passe par un calcul intermédiaire très coûteux. La seconde est beaucoup plus efficace. Reprenons notre fonction d'exponentiation rapide en y ajoutant le modulo.
ENTRÉES a, b et q, entiers positifs
SORTIE a^b mod q
DÉBUT
r prend la valeur 1
p prend la valeur a mod q
TANT QUE b > 0 RÉPÉTER
SI b mod 2 = 1 ALORS
r prend la valeur r * p mod q
FIN
p prend la valeur p * p mod q
b prend la valeur b // 2
FIN
RENVOYER r
FIN
À faire : Écrire la fonction exponentiation_mod(a, b, q). Vérifier que puissance_rapide_mod(3, 100, 43) renvoie bien le 23 attendu.
Pour aider, détail de l'exécution. Vous pouvez voir que le calcul complet se fait en une trentaine d'exécution sans jamais utiliser de grand nombre.
a = 3, b = 100, q = 43
| ligne | effet |
|---|---|
| 4 | r = 1 |
| 5 | p = 3 |
| 6 | b > 0 → boucle s'exécute |
| 7 | b % 2 == 0 → SI ne s'exécute pas |
| 10 | p = p*p % 43 = 9 |
| 11 | b = b // 2 = 50 |
| 6 | b > 0 → boucle s'exécute |
| 7 | b % 2 == 0 → SI ne s'exécute pas |
| 10 | p = p*p % 43 = 38 |
| 11 | b = b // 2 = 25 |
| 6 | b > 0 → boucle s'exécute |
| 7 | b % 2 == 1 → SI s'exécute |
| 8 | r = r*p % 43 = 38 |
| 10 | p = p*p % 43 = 25 |
| 11 | b = b // 2 = 12 |
| 6 | b > 0 → boucle s'exécute |
| 7 | b % 2 == 0 → SI ne s'exécute pas |
| 10 | p = p*p % 43 = 23 |
| 11 | b = b // 2 = 6 |
| 6 | b > 0 → boucle s'exécute |
| 7 | b % 2 == 0 → SI ne s'exécute pas |
| 10 | p = p*p % 43 = 13 |
| 11 | b = b // 2 = 3 |
| 6 | b > 0 → boucle s'exécute |
| 7 | b % 2 == 1 → SI s'exécute |
| 8 | r = r*p % 43 = 21 |
| 10 | p = p*p % 43 = 40 |
| 11 | b = b // 2 = 1 |
| 6 | b > 0 → boucle s'exécute |
| 7 | b % 2 == 1 → SI s'exécute |
| 8 | r = r*p % 43 = 23 |
| 10 | p = p*p % 43 = 9 |
| 11 | b = b // 2 = 0 |
| 6 | b == 0 → boucle terminée |
| 13 | renvoie r = 23 |
Utiliser 3**100 % 43 peut sembler plus rapide. Il faut bien identifier les choses : Le calcul 3**100 utilisera une sorte de boucle for cachée bien plus rapide que la boucle for disponible sous Python. Mais notre fonction utilise la boucle for Python et s'en trouve handicapée.
Mais nous ne devons pas raisonner ainsi. Nous utilisons Python parce que c'est un langage plus facile pour débuter. Si nous voulions de la performance, nous utiliserions un langage plus performant et plus proche de la machine, par exemple le Go ou le C. Ce serait plus difficile car il faudrait tout définir : En C on n'a pas de fonction puissance ou d'entiers arbitrairement longs… On ne pourrait pas écrire 3**100 % 43, il faudrait l'implémenter et l'implémentation la plus efficace serait celle présentée ci-dessus.