zzz

import math

def euclides2(x,y):
    temp = 0
    coeff = 0
    rest = -1
    while rest != 0:
        if (x > y):
            rest = x % y
            coeff = math.floor(x/y)
            print(str(x) + ' = ' + str(coeff) + '*' + str(y) + ' + ' + str(rest) + ' -> ' +
                  str(rest) + ' = ' + str(x) + ' - (' + str(y) + '*' + str(coeff) + ')')
            x = y
            y = rest
        else:
            rest = y % x
            coeff = math.floor(y/x)
            print(str(y) + ' = ' + str(coeff) + '*' + str(x) + ' + ' + str(rest) + ' -> ' +
                  str(rest) + ' = ' + str(y) + ' - (' + str(x) + '*' + str(coeff) + ')')
            y = x
            x = rest


# Rozklad na czynniki pierwsze
# Zwraca w liscie, od gory
def distribution(x):
    ite = 2
    dividers = []
    while x > 1:
        if x % ite == 0:
            temp = x
            x /= ite
            dividers.append(ite)
            print(str(temp) + '  |  ' + str(ite))
            ite = 2
        else:
            ite += 1
    return dividers


# Strukturyzja do postaci slownika klucz-wartosc
# Gdzie klucz to podstawa, a wartosc wykladnik (ilosc wystapien poszczegolnego dzielnika w rozkladzie)
def structurize_divs(divers):
    result = {}
    for i in divers:
        result[i] = divers.count(i)
    return result


# Funkcja Eulera (nie twierdzenie)
def euler(x):
    arr = distribution(x)
    data = structurize_divs(arr)
    result = 1
    for base in data:
        result *= pow(base, data[base] - 1) * (base - 1)
        print(str(base)+'^('+str(data[base])+'-1)'+'*('+str(base)+'-1)', end=' * ')
    print('\n')
    print('Wynik wynosi : ' + str(result))


def leftright(x, power, mod):
    # Konwersja na binarke do listy
    bins = [int(i) for i in list('{0:0b}'.format(power))]
    it1 = 0
    it2 = 1
    it3 = len(bins)-1
    z = 0
    z = (pow(pow(x, bins[it1]), 2)) % mod
    print('w' + str(it2) + ' = (' + str(x) + '^(n' + str(it3) + '))^2 mod' + str(mod) + ' = ' + str(z))
    it1 += 1
    it2 += 1
    it3 -= 1
    y = (z*pow(x, bins[it1])) % mod
    print('w' + str(it2) + ' = ' + str(z) + '*' + str(x) + '^(n' + str(it3) + ') mod' + str(mod) + ' = ' + str(y))
    it1 += 1
    it2 += 1
    it3 -= 1
    print('\n')
    while it1 < len(bins):
        z = (pow(y, 2)) % mod
        print('w' + str(it2) + ' = ' + str(y) + '^2 mod' + str(mod) + ' = ' + str(z))
        it2 += 1
        y = (z * pow(x, bins[it1])) % mod
        print('w' + str(it2) + ' = ' + str(z) + '*' + str(x) + '^(n' + str(it3) + ') mod' + str(mod) + ' = ' + str(y))
        print('\n')
        it1 += 1
        it2 += 1
        it3 -= 1

def rightleft(x, power, mod):
    # Konwersja na binarke do listy
    bins = [int(i) for i in list('{0:0b}'.format(power))]
    z = 0
    y = 0
    n = len(bins)-1
    i = 1
    ni = 0
    z = x % mod
    print('z'+str(i)+' = '+str(x)+'^(2^0) mod'+str(mod)+' = '+str(z))
    y = (pow(z, bins[n])) % mod
    print('y'+str(i)+' = 1*'+str(x)+'^(n'+str(ni)+') mod'+str(mod)+' = '+str(y)+'\n')
    n -= 1
    i += 1
    ni += 1
    while n >= 0:
        tempz = z
        tempy = y
        z = (pow(z, 2)) % mod
        print('z'+str(i)+' = '+str(tempz)+'^(2) mod'+str(mod)+' = '+str(z))
        y = (y*pow(z, bins[n])) % mod
        print('y' + str(i) + ' = ' + str(tempy) + '*' + str(z) + '^(n' + str(ni) + ') mod' + str(mod) + ' = ' + str(y)+'\n')
        n -= 1
        i += 1
        ni += 1


def modulcalc(x, mod):
    middle = math.floor(x/mod)
    result = x - (middle*mod)
    print(str(x)+'mod'+str(mod)+' = '+str(x)+' - ['+str(x)+'/'+str(mod)+']*'+str(mod)+' = '+str(result))

# Aby uzyc wystarczy wpisac odpowiednia funkcje i skompilowac program, funkcje dostepne opisane sa ponizej

# Przyklad uzycia : na dole dopisuje modulcalc(135,5), daje Run - otrzymuje wynik, jak w matlabie.

# Funkcje do uzycia:
# Modulo (z ujemnymi tez) - modulcalc(x,mod), gdzie x to liczba, mod liczba modulo pokazuje zapis
# NWD - euclides2(x,y) gdzie x,y to liczby dla ktorych liczone jest NWD
# Funkcja Eulera - euler(x) gdzie x to liczba z ktorej jest funkcja, ostatnia gwiazdke w zapisie poteg ignoruj
# Metoda z lewa na prawo - lefright(x, power, mod) gdzie x to liczba, power wykladnik, mod to wartosc modulo
# Metoda z prawa na lewo - rightleft(x, power, mod) - tak samo jak z lewa na prawo

rightleft(3,64,11)