Arithmétique - Exponentiation rapide

I) Présentation

  On étudie ici le très classique et très efficace algorithme d'exponentiation rapide qui permet le calcul d'une puissance à exposant entier, éventuellement modulo p. Il est ici présenté pour des calculs de puissances d'entiers ou de flottants, mais il s'adapte sans difficultés à des calculs de puissances de matrices, par exemple.

  L'objectif est de calculer f ( a , n ) = a n ou f_mod ( a , n , p ) = a n [ p ] pour a N * (éventuellement a R * ) , n N et p N *

  L'idée qu'exploite cet algorithme est la suivante: le calcul de a 2 n ou de a 2 n + 1 se ramène à celui de a n en remarquant que: { a 2 n + 1 = a * ( a n ) 2 a 2 n = ( a n ) 2 pour a , n N .

II) Algorithme

def f(a, n):
    """exponentiation rapide (calcul de a^n). Version itérative"""
    b, m = a, n
    r = 1
    while m > 0:
        if m % 2 == 1:
            r = r * b
        b = b * b
        m = m //2
    return r

III) Terminaison, correction et complexité

Pour k N * , on note r k , b k et m k les valeurs des variables r, b, m après l'exécution de la k ième itération de la boucle while. On note r 0 , b 0 et m 0 les valeurs de r, b et m avant l'exécution de la première itération.

Q1) Donner les valeurs de r 0 , b 0 et m 0 .

Q2) Pour k N * , écrire les relations exprimant   r k , b k et m k en fonction de r k - 1 , b k - 1 et m k - 1 , en distinguant le cas où m k - 1 = 2 p   est pair et le cas où m k - 1 = 2 p + 1   est impair.

Q3) Dans les cas où n = 6, puis n = 19, remplir et compléter un tableau (en prenant modèle sur le tableau suivant) en donnant les valeurs de   r k , b k et m k jusqu'à la dermière itération lors du calcul de f(a, 6) puis de f(a, 19).

   k=0      k=1       k=2     ...
r k              
b k              
m k              

Dans la suite n est un entier quelconque de N * .

Q4) Démontrer que l'algorithme se termine.

Q5) On démontre la correction de l'algorithme d'exponentiation rapide. On note P ( k ) la propriété    P ( k ) : a n = r k b k m k .

  Q5a) Prouver P ( 0 )

  Q5b) Pour k N * , prouver que P ( k - 1 ) P ( k )   lorsque la k ième itération a lieu.

  Q5c) En déduire que f ( a , n ) = a n et la correction de l'algorithme.

Q6) Le coût C f ( n ) de l'algorithme f ( a , n ) est le nombre total de multiplications effectuées.

  Q6a) Prouver que  pour k N , m k n 2 k lorsque la k ième itération a lieu.

  Q6b) En déduire que   C f ( n ) 2 [ ln ( n ) ln ( 2 ) ] + 2 .

  Q6c) En déduire que  la complexité  de l'algorithme d'exponentiation rapide est en O ( ln ( n ) ) .

Conclusion: l'algorithme d'exponentiation rapide est un algorithme de complexité O ( ln ( n ) ) multiplications, bien meilleur que l'algorithme naïf de calcul de puissance qui lui nécessite n multiplications.

def puissance_naif(a,n):
    r = 1
    for i in range(n):
        r = r * a
    return r

Q7) Ecrire une version récursive de l'algorithme d'exponentiation rapide.

IV) Exponentiation rapide modulaire

C'est une fonction indispensable par exemple pour la méthode de chiffrement RSA.

On veut calculer f_mod ( a , n , p ) = a n [ p ] pour a , p N * et n N .

Q8) Pourquoi est-ce une très mauvaise idée de définir:

def f_mod1(a, n, p):
    return f(a, n) % p

Q9) Définir la fonction f_mod(a, n, p)  efficacement.

Vérifier par exemple que 311111 10 10 = 19 [ 79 ]

Q10) Calculer par exemple les durée du calcul de 1000001^1000001 [189] avec f_mod1() et f_mod() pour voir le gain de temps.

import time    
    ....
    t = time.perf_counter()
    f_mod(a, n, p)
    t1 = time.perf_counter() -t
    ....

© 2014 - Eric Obermeyer      Powered by      Corrigé