p = 2
N = 11
q = 7
d = 2

R.<i> = PolynomialRing(ZZ)
RR.<g> = R.quotient(i^N-1)

T.<s> = PolynomialRing(QQ)
TT.<u> = T.quotient(s^N-1)

Rpt.<h> = PolynomialRing(GF(p))
Rp.<j> = Rpt.quotient(i^N-1)

Rqt.<k> = PolynomialRing(GF(q))
Rq.<l> = Rqt.quotient(i^N-1)

def randomTrinaryPoly(d1,d2):
    if d1+d2 < N:
        tmpTab = [0]*N
        x = 0
        indexArray = []
        for i in range(0,N):
            indexArray.append(i)
        while x < d1:
            tmpIndex = randint(0,N-1)
            if tmpIndex in indexArray:
                tmpTab[tmpIndex] = 1
                indexArray.remove(tmpIndex)
                x+=1
        x = 0
        while x < d2:
            tmpIndex = randint(0,N-1)
            if tmpIndex in indexArray:
                tmpTab[tmpIndex] = -1
                indexArray.remove(tmpIndex)
                x+=1
        return R(tmpTab)

def roundCoeffs(poly):
    tmpTab = []
    for c in poly:
        tmpTab.append(round(c))
    return R(tmpTab)

def ntruGen():
    f = randomTrinaryPoly(d+1,d)
    g = randomTrinaryPoly(d,d)
    while True:
        f = randomTrinaryPoly(d+1,d)
        g = randomTrinaryPoly(d+1,d)

        Rf,f1,f2 = xgcd(f,i^N-1)
        Rg,g1,g2 = xgcd(g,i^N-1)

        if gcd(f,g) == 1 and gcd(Rf,Rg) == 1:
            break
    return f,f1,f2,g,g1,g2,Rf,Rg



while True:
    f,f1,f2,g,g1,g2,Rf,Rg = ntruGen();
    if gcd(Rf,Rg) == 1:
        break
temp,sf,sg = xgcd(Rf,Rg)
A = q*sf*f1
B = -q*sg*g1

fr = TT(f)**-1
gr = TT(g)**-1

C = roundCoeffs((TT(B)*fr+TT(A)*gr)/2)
F = TT(B-C*f)
G = TT(A-C*g)

print F