bva7

from datetime import datetime

CONST_MENU = "Введите номер команды\n" \
    "1 - Трюк Шамира\n" \
    "2 - Бинарный метод\n" \
    "3 - Встроенные функции Sage\n" \
    "4 - Выход\n"


def sum_points(P, Q, E, p):
    xP, yP, zP = lift(P[0]), lift(P[1]), lift(P[2])
    xQ, yQ, zQ = lift(Q[0]), lift(Q[1]), lift(Q[2])

    U = yQ * zP - yP
    UU = U * U
    V = xQ * zP - xP
    VV = V * V
    VVV = V * VV
    R = VV * xP
    A1 = UU * zP - VVV - 2 * R

    xG = A1 * V
    yG = U * (R - A1) - VVV * yP
    zG = VVV * zP
    zG_inv = inverse_mod(zG, p)
    return E((xG* zG_inv) % p, (yG* zG_inv) % p, (zG * zG_inv) % p)

def bin_alg(P, k, E):
    t = len(bin(k)) - 2
    #t = int(ceil(log(k, 2)))
    Q_inf = E(0, 1, 0)
    binary_form_k = bin(k)[2::]
    for i in range(0, t):
        Q_inf = 2 * Q_inf
        if binary_form_k[i] == '1':
            Q_inf = Q_inf + P
    return Q_inf

def NAF(k):
    NAF_k = []
    while k >= 1:
        k_i = 0
        if k & 1 == 1:
            k_i = 2 - (k % 4)
            k -= k_i
        k >>= 1
        NAF_k.append(k_i)
    return NAF_k

def Shamir_NAF(k1, k2, G, Q, E):
    k1_bin = NAF(k1)
    k2_bin = NAF(k2)
    print(k1_bin)
    print(k2_bin)
    i = max(len(k1_bin) - 1, len(k2_bin) - 1)
    R = E(0, 1, 0)
    while i >= 0:
        R = 2 * R
        if i < len(k1_bin):
            if k1_bin[i] > 0:
                R += G
            elif k1_bin[i] < 0:
                R -= G
        if i < len(k2_bin):
            if k2_bin[i] > 0:
                R += Q
            elif k2_bin[i] < 0:
                R -= Q
        i -= 1
    return R


def show_sage_results(G, Q, E, k1, k2):
    start_time = datetime.now()
    res = k1 * G + k2 * Q
    print("Sage:\nСумма кратных точек равна {}, время выполнения - {}" .
          format(res, datetime.now() - start_time))


def main():
    p = 115792089237316193816632940749697632394964361042935191217416087735021737577431
    A = 39911043712488959346023488649471543779004688285304668897256090422321915164205
    B = 26607362474992639564015659099647695852669792190203112598170726948214610109470
    xG = 1
    yG = 11226734598496010064741041559038474696573800958032815190522914592034679115175
    E = EllipticCurve(GF(p), [A, B])
    xQ = 38629820510180468045357408584494165586311762354959716428253674833800185794409
    yQ = 47209116219363615180726774296092433536731216531642727785409102267320788176038
    G = E(xG, yG)
    Q = E(xQ, yQ)

    k1 = 2 ** 64
    k2 = 222220000022222000002222200000
    while 1:
        user_choice = input(CONST_MENU)
        if not user_choice.isdigit():
            continue
        user_choice = int(user_choice)
        if user_choice == 1:
            start_time = datetime.now()
            res = Shamir_NAF(k1, k2, G, Q, E)
            print("Трюк Шамира с NAF: {}, время выполнения - {}" .
                  format(res, datetime.now() - start_time))
        elif user_choice == 2:
            start_time = datetime.now()
            resG = bin_alg(G, k1, E)
            resQ = bin_alg(Q, k2, E)
           # print(resG)
           # print(resQ)
            sum = sum_points(resG, resQ, E, p)
            print("Сумма кратных точек: {}, время выполнения - {}" .
                  format(sum, datetime.now() - start_time))
        elif user_choice == 3:
            show_sage_results(G, Q, E, k1, k2)
        elif user_choice == 4:
            return

main()