from random import randint

def get_T(z,k):
    if k==10:
        return 3+5*z+10*z**2,3-5*z+10*z**2
    elif k==6:
        return 1+2*z,1-2*z
def get_p(z,k):
    if k==10:
        return 25*z**4+25*z**3+25*z**2+10*z+3
    elif k==6:
        return 4*z**2+1
def get_r(z,k):
    if k==10:
        return 25*z**4+25*z**3+15*z**2-5*z+1,25*z**4+25*z**3+15*z**2+5*z+1
    elif k==6:
        return 4*z**2-2*z+1,4*z**2+2*z+1
def genParams(k):
    z = 2
    while True:
        p = get_p(z,k)
        if p in Primes():
            r1,r2 =get_r(z,k)
            if r1 in Primes():
                r = r1
                T,g = get_T(z,k)
                break
            elif r2 in Primes():
                r = r2
                g,T = get_T(z,k)
                break
        z = z + 1
    print "k = {}".format(k)
    print "z = {}".format(z)
    print "Trace T : {}".format(T)
    print "Char p = {}".format(p)
    print "Count of points r = {}".format(r)
    return z,r,T,p
def gen_A(j,K):
    return K(3*j / (1728 - j))
def gen_B(j,K):
    return K(2*j / (1728 - j))
def genCurve(k):
    z,r,T,p = genParams(k)
    D = 4*p - T**2
    H = hilbert_class_polynomial(-D) #Получаем полином Гильберта
    K = GF(p)
    roots = H.roots(ring = K, multiplicities = False)
    if (roots == []):
        return '', ''
    print(roots)
    j = roots[0]
    print "j = {}".format(j)

    A = gen_A(j,K)
    B = gen_B(j,K)
    E = EllipticCurve(K, [A,B])
    if E.order() != r:
        return '', '', 0

    print "Nice. {}".format(E)

    KK.<t> = GF(p**k)
    EK = EllipticCurve(KK, [A, B])
    if gcd(EK.order(), r**2) == 1:
        return '', '', 0
    print "Nice. {}".format(EK)
    return E, EK, r


def genKRGroup(P, Q, r):
    table = []
    for i in range (1, r):
        row = []
        P_i = i*P
        for j in range (1, r):
            Q_j = j*Q
            row.append(P_i + Q_j)
        table.append(row)
    print 'P+Q {}'.format(table[0][0])
    print 'P+2Q {}'.format(table[0][1])
    print '2P+Q {}'.format(table[1][0])
    print '2P+2Q {}'.format(table[1][1])
    print 'P = {}\nQ = {}'.format(P,Q)
    return table
def getWeil(EK, KRgroup, r):
    res = []
    S1 = KRgroup[randint(0, r - 2)][randint(0, r - 2)]
    S2 = KRgroup[randint(0, r - 2)][randint(0, r - 2)]
    T  = KRgroup[randint(0, r - 2)][randint(0, r - 2)]
    S1_S2 = S1 + S2
    S1S2T = S1_S2.weil_pairing(T,r)
    S1T = S1.weil_pairing(T, r)
    S2T = S2.weil_pairing(T, r)
    resS1S2T = S1T*S2T
    if S1S2T == resS1S2T:
        res.append("+");
    else:
        res.append("-");

    P_0 = EK([0, 1, 0])
    S1P = S1.weil_pairing(P_0,r)
    PS1 = P_0.weil_pairing(S1,r)
    if S1P == PS1 == 1:
        res.append("+");
    else:
        res.append("-");

    TT = T.weil_pairing(T,r)
    if TT == 1:
        res.append("+");
    else:
        res.append("-");
    return res

def getTate(EK, KRgroup, r, k):
    res = []
    S1 = KRgroup[randint(0, r - 2)][randint(0, r - 2)]
    S2 = KRgroup[randint(0, r - 2)][randint(0, r - 2)]
    T  = KRgroup[randint(0, r - 2)][randint(0, r - 2)]
    S1_S2 = S1 + S2
    S1S2T = S1_S2.tate_pairing(T,r,k)
    S1T = S1.tate_pairing(T,r,k)
    S2T = S2.tate_pairing(T,r,k)
    resS1S2T = S1T*S2T
    if S1S2T == resS1S2T:
        res.append("+");
    else:
        res.append("-");

    P_0 = EK([0, 1, 0])
    S1P = S1.tate_pairing(P_0,r,k)
    PS1 = P_0.tate_pairing(S1,r,k)
    if S1P == PS1 == 1:
        res.append("+");
    else:
        res.append("-");

    TT = T.tate_pairing(T,r,k)
    if TT == 1:
        res.append("+");
    else:
        res.append("-");
    return res

def calcHash(string, p):
    res = 0
    for i in string:
        res = res + ord(i)
    return res % p

def createEKP(string, EK):
    p = int(EK.base_field().characteristic())
    A = int(EK.a4())
    B = int(EK.a6())
    KT = GF(p)
    for i in range(2, p):
        h = calcHash(string, i)
        t = kronecker_symbol(h**3 + A*h + B, p)
        if t == 1:
            var('y')
            x = h
            E = x**3 + A*x + B == y**2
            y_res = E.roots(ring = KT, multiplicities = False)
            yr = y_res[randint(0, p) % len(y_res)]
            try:
                P = EK([h, yr])
                return P
            except:
                continue
    P0 = EK([0,1,0])
    return P0

def genSign(string, EK, KRgroup, r):
    M = createEKP(string, EK)
    a = randint(1, r - 1)
    sign = a * M
    P = KRgroup[randint(0, r - 2)][randint(0, r - 2)]
    T = a * P
    print 'M = {}'.format(M)
    print 'a = {}'.format(a)
    print 'a*M = {}'.format(sign)
    print 'Point from gr. kr. {}'.format(P)
    print 'a*P = {}'.format(T)
    return sign[0], P, T

def checkSign(string, EK, torsion_group, r, Xs, P, T):
    KT = GF(EK.base_field().characteristic())
    A = int(EK.a4())
    B = int(EK.a6())
    Ytau = KT(Xs**3 + A*Xs + B)
    Ytau = KT(sqrt(Ytau))
    try:
        T1 = EK([Xs, Ytau])
    except:
        Ytau = KT(-Ytau)
        T1 = EK([Xs, Ytau])
    M = createEKP(string, EK)
    print 'M = {}'.format(M)
    print 'T1 = {}'.format(T1)
    P1 = P.weil_pairing(T1, r)
    P2 = T.weil_pairing(M, r)
    if (P1 == P2) or (P1 == P2^(-1)):
        print 'Sign correct'
    else:
        print 'Sing incorrect'


if __name__ == "__main__":
    k = 6
    E, EK, r = genCurve(k)
    if r == 0:
        print 'error: 1 step .GEN '
    P = EK([13,13,1])
    KT.<t> = GF(EK.base_field().characteristic()).extension(k)
    KT = EK.base_field()
    Q = EK([KT(10*t^3 + 6*t^2 + 15*t + 12), KT(8*t^5 + 12*t^4 + 3*t^3 + 4*t + 1), KT(1)])
    KR_group = genKRGroup(P, Q, r)
    res1 = getWeil(EK, KR_group, r)
    res2 = getTate(EK, KR_group, r, k)
    print("\t\tВейля\tТейта\t")
    print "Билин-ть\t {} \t {} \t".format(res1[0],res2[0])
    print "Знакоп-ть\t {} \t {} \t".format(res1[2],res2[2])
    print "Невырож.\t {} \t {} \t".format(res1[1],res2[1])

    print 'Short sign'
    string = 'My life is pain'
    signn, P, T = genSign(string, EK, KR_group, r)
    print "SIGN : {}".format(signn)
    checkSign(string, EK, KR_group, r, signn, P, T)