====== 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 [[nsi:terminales: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 :

<code lang-none linenums>
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
</code>

<WRAP box>
**À faire :** écrire la fonction Python ''%%exponentiation_naive(a, b)%%'' implémentant cet algorithme.

Vérifiez que :
<code language=python>
assert exponentiation_naive(3,100) == 3**100
</code>
</WRAP>

==== 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$$

{{ expo_3.png?nolink&600 |}}

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 [[nsi:premiere:numeration|décomposition binaire]] : $100 = 1100100_2$. On reconnaît donc dans l'algorithme suivant une méthode de **division successives**.

<code lang-none linenums>
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
</code>

<WRAP tip>
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.
</WRAP>

<WRAP box>
**À faire :** Écrire la fonction ''%%exponentiation_rapide(a, b)%%''

Vérifiez que :
<code language=python>
assert exponentiation_rapide(3,100) == 3**100
</code>
</WRAP>

===== Exponentiation modulaire =====

On souhaite calculer $a^b \mod p$. La cryptographie fait grand usage de ce calcul.

{{page>nsi:terminales:chiffrement_modulo#Rappel de ce qu'est modulo}}

{{page>nsi:terminales:chiffrement_modulo#Multiplications modulo}}

==== 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.

<code python>
>>> 3**100
515377520732011331036461129765621272702107522001
>>> 515377520732011331036461129765621272702107522001 % 43
23
</code>

  * 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.

<code lang-none linenums>
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
</code>


<WRAP box>
**À faire :** Écrire la fonction ''%%exponentiation_mod(a, b, q)%%''. Vérifier que ''%%puissance_rapide_mod(3, 100, 43)%%'' renvoie bien le 23 attendu.
</WRAP>

<WRAP box>
**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''                        |
</WRAP>

<WRAP tip>
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 [[nsi:langages:go:start|Go]] ou le [[nsi:langages:c:start|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.
</WRAP>