Méthode binaire

Lorsque $ x = a ^ k $, le calcul du carré est effectué $ k $ fois. Pour rendre le calcul efficace, la méthode binaire consiste à limiter le montant du calcul à $ log (k) $ en trouvant séquentiellement $ a ^ {2 ^ i} $.

Exemple concret

5^{21}=5^{2^4}*5^{2^2}*5^{2^0}

Le calcul est exécuté en développant un nombre binaire et en développant dans l'ordre à partir de la gauche. En conséquence, $ g ^ k (mod p) $ est calculé.

algorithme

`binary.py`


def Binary(k, g, p):
    k_binary = []
    while(k != 0):
        k_binary.append(k%2)
        k = k//2
        if k == 1:
            k_binary.append(k)
            k = 0
    y = 1
    for i in reversed(range(len(k_binary))):
        if k_binary[i] == 1:
            y = (y*y%p)*g%p
        else:
            y = (y*y%p)
    return y