Binary method

Binary method

When $ x = a ^ k $, the square calculation is performed $ k $ times. The binary method is a method to reduce the amount of calculation to $ log (k) $ by sequentially finding $ a ^ {2 ^ i} $ as a method to make the calculation efficient.

Concrete example

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

The calculation is executed by expanding to a binary number and expanding in order from the left. As a result, $ g ^ k (mod p) $ is calculated.

algorithm

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

Binary method
Manim's method 7
Manim's method 13
Manim's method 2
Manim's method 18
Manim's method 5
Manim's method 3
Manim's method 15
Manim's method 11
Manim's method 16
Manim's method 10
Manim's method 9
Manim's method 6
Manim's method 21
Manim's method 4
Manim's method 8
Manim's method 14
Manim's method 22
Manim's method 19
Manim's method 12
Special method
Special method
Understand k-means method
Clustering of clustering method
Manim's method part 23
Dictionary items method
[PyTorch] Installation method
N cross method
Image collection method
visualize binary search
ABC146C (binary search)
Regression analysis method
Gradient method implementation 1
Python-peewee connection method
Class method static method
youtube-dl update method
Monte Carlo method
Mode-Matching Method Simulation_Python
Johnson method (python)
[Python] Semi-Lagrange method