Méthode binaire

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

Recommended Posts

Méthode binaire
Méthode spéciale
Méthode spéciale
Comprendre la méthode k-means
Clustering de méthodes de clustering
Méthode des éléments du dictionnaire
[PyTorch] Comment installer
Méthode croisée N
Méthode de collecte d'images
visualiser la recherche binaire
ABC146C (dichotomie)
Méthode d'analyse de régression
Implémentation de la méthode de gradient 1
Méthode de connexion Python-peewee
Méthode de classe Méthode statique
méthode de mise à jour youtube-dl
Méthode de Monte Carlo
Méthode de correspondance de mode Simulation_Python
Méthode Johnson (python)
[Python] Méthode Semi-Lagrange