Quotient symbolic polynomial ring

edit

Yep,

thanks, that works like a magic trick. Yet I still have some minor problems. I append the whole code in below

def HFEkeyGeneration(n,q):

#Initializes basic structures
k = GF(q)
R = PolynomialRing(k, 'x', n)

#Initializes random affine transformations S = (A,c), T = (B,d)
A = random_matrix(k, n, n)
while A.is_singular():
    A = random_matrix(k,n,n)

B = random_matrix(k,n,n)
while B.is_singular():
    B = random_matrix(k,n,n)   

c = random_vector(k,n)
d = random_vector(k,n)

#The general vector we encrypt    
m = vector(R,n,R.gens())

#Apply S to message
m = A*m
m = m + c

#Transforms vector to list and reverses it
list = m.list()
list.reverse()

#Setup of quotient ring
P.<x> = PolynomialRing(k)
g = P.irreducible_element(n)

L.<y> = PolynomialRing(R)
pol = L(list)

g = L(g)
print g
I = L.ideal([g])
Q = L.quotient_ring(I)

#Apply of fixed secret polynomial
pol = Q(pol^(2*q) + pol^q + 1)

#Transforms polynomial back to vector    
list = pol.list()
list.reverse()
m = vector(R,n,list)

#Apply affine transformation T
m = B*m
m = m + d


#print "setup"
#print "Affine transformation T is:"
#print A
#print c
#print "Affinte transformation S is:"
#print B
#print d
#print "Length of message is: %d" %n
#print "The secret polynomial is:"
#print p

print m
return m

The thing is, that The part, when I power the polynomial, i.e. Q(pol^(2*q) + pol^q + 1) should be randomized. That means, that I choose pseudorandom polynomial and then evaluate 'pol' in it. I was not able to achieve that. Also, the output polynomial of this operation is of very special form. The indeterminates in coefficients are of powers either x^q (where q is cardinality of field I work in) or simply x. Yet, in finite field q, the x^q = x. I would need to rewrite the polynomial, so that every term in coefficient, where x^q appears, would be written as x.

The problem is, that I've never worked with sage before and perhaps I never will in future. So I'm just putting the code together.