Ask Your Question

Quotient symbolic polynomial ring

asked 2016-04-26 13:39:17 -0600

AJey gravatar image


I have troubles to state this question percisely, though I do my best. I have two affine transformations S,T (size n) and univariate polynomial P - all over finite field k. The univariate polynomial is a member of quotient ring k[t]/<g>, where g is irreducible polynomial of degree n. I am computing S(P(T(m)), where m is message of length n. So, first I perform affine transformation on m, then I transform the result to polynomial ring by coefficients. Example follows

m = (1,0,1), S(M) = (1,1,0). Then corresponding polynomial is x^2 + x + 0. Then I evaluate P in value x^2 + x + 0. So I compute P(x^2 + x), where computation is done modulo g. Let's say, that result is 0x^2 + x + 1. Then I transfer this back to vector, again by coefficients. So the resulting vector is (0,1,1). Finaly I apply last affine transformation T.

The problem is, that I need to be able to do this for general looking vectors, i.e. for vectors (m_1, ... , m_n). I'm newbie to sage. I tried to create symbolic vector with elements m_0 , ... , m_n. Then successfuly applied first transformation and was able to make a polynomial out of that vector.

What I struggle with, is evaluating the polynomial P on that vector. First of all, I'm not even able to create the corresponding quotient ring. I guess that my polynomial ring is PolynomialRing(SR, 't'). Yet, sage won't let me create irreducible element of this ring. I'm not sure whether I've chosen the right path how to tackle this problem.

Could please anyone provide some insight and perhaps suggest how to proceed?


edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted

answered 2016-04-26 17:19:52 -0600

tmonteil gravatar image

updated 2016-04-26 18:49:02 -0600

A common trick in such cases is not to consider m_1, ... , m_n as symbols (elements of the symbolic ring), but as indeterminates of some polynomial ring, which is a genuine ring on which algebra works much better.

For example, with n=10, you can do:

sage: R = PolynomialRing(QQ,10,'m_')
sage: R
Multivariate Polynomial Ring in m_0, m_1, m_2, m_3, m_4, m_5, m_6, m_7, m_8, m_9 over Rational Field
sage: R.inject_variables()
Defining m_0, m_1, m_2, m_3, m_4, m_5, m_6, m_7, m_8, m_9

Could you try with this, and tell if it works (or provide precise code on where it blocks) ?

edit flag offensive delete link more

answered 2016-04-27 02:30:30 -0600

AJey gravatar image

updated 2016-04-27 02:47:56 -0600


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()

#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()
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.

edit flag offensive delete link more


I am not sure i understand you new question. If you want to create a random polynomial, if R denotes the polynomial ring, you can do:


Also, if you want to tell that x^q equals x, you can work in the quotient ring x^q-x (for this, you can define I=R.ideal(x^q-x)).

tmonteil gravatar imagetmonteil ( 2016-04-27 05:08:45 -0600 )edit

Well, that won't go that easy. I need to specify, that x^q equals x for every variable x0, ... , xn.

AJey gravatar imageAJey ( 2016-04-27 05:31:50 -0600 )edit

It is actually easy because of the expressive power of Python list comprehensions: you can get the generators of R (that is the indeterminates) with R.gens(), so you can make the list you want with [x^q-x for x in R.gens()], hence you can define your ideal with:

sage: R.ideal([x^q-x for x in R.gens()])

For a conctete example:

sage: q=3
sage: n=10
sage: k = GF(q)
sage: R = PolynomialRing(k, 'x', n)
sage: R.ideal([x^q-x for x in R.gens()])
Ideal (x0^3 - x0, x1^3 - x1, x2^3 - x2, x3^3 - x3, x4^3 - x4, x5^3 - x5, x6^3 - x6, x7^3 - x7, x8^3 - x8, x9^3 - x9) of Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 over Finite Field of size 3
tmonteil gravatar imagetmonteil ( 2016-04-27 07:39:54 -0600 )edit

Note that what is interesting in Sage is that even if you do not plan to work with it in the future, at least it is a way to learn Python, a nice general-purpose language, that could be useful in many other situations.

tmonteil gravatar imagetmonteil ( 2016-04-27 07:46:27 -0600 )edit

Again, works like a charm. Yo, got your point. I'm more of a C person, yet in math computing python is important I guess. I'm facing (hopefully) final problem. That is, is it possible in finite field to avoid negatvie representation of integers? i.e. to convert in GF(5) expression -2 to 3 etc.?

AJey gravatar imageAJey ( 2016-04-27 10:15:23 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2016-04-26 13:39:17 -0600

Seen: 63 times

Last updated: Apr 27 '16