AJey's profile - activity

Yep, for polynomials with coefficients in GF(q) The sage naturally decides to print the lower number, i.e. -2 instead of 3 in case of GF(5).

I work with arbitrary finite field GF(q), for q power of prime. I've been looking around for some function, which would force, that any element is printed as a positive natural number. i.e. in GF(5), -2 is printed as 3 etc. Is that possible in an easy way? I need to achieve that for arbitraty q. I've been thinking about writing some own function, but it seems intractable for me at the moment.

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.?

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

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.

Hello,

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?

Thanks

Hello,

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?

Thanks