Finite_Field_F_27

# To set up the field of order q = 3^3 p, n = 3, 3 

q = p^n 

# For Stinson Exercise 6.12 we can't use Sage's built-in GF(27) ... F.<x> = GF(q); F 

# ... because the built-in modulus is not the one used by Stinson! F.modulus() 

# So we set up the field explicitly as a quotient field mod # the primitive irreducible polynomial we want. F3 = GF(3) R.<x> = PolynomialRing(F3) f = R(x^3+2*x^2+1) 

f.is_irreducible(), f.is_primitive() 

F27 = QuotientRing(R, f(x)); F27 

F27.is_field() 

# Here is the public key given by Stinson. # Notice that in F27, x is called xbar. print F27(x^11) F27(x^11).lift() 

############################################# # # This will save you the chore of typing in # the correspondence between letters of the # alphabet and elements of F27*. # # Get the nonzero elements and sort them # lexicographically. # First define the comparison function # It represents polynomials as lists of # coefficients and sorts. def cmp(u, v): """Compare polynomials lexicographically.""" ul, vl = u.list(), v.list() i, cp = 2, False while i >= 0 and not cp: if ul[i] < vl[i]: r, cp = -1, True elif ul[i] > vl[i]: r, cp = 1, True else: i -= 1 if not cp: r = 0 return int(r) 

F27star =[F27(x^i) for i in range(26)] F27star.sort(cmp=cmp) 

# The result expresses the powers as polynomials in "xbar" # which is not defined. F27star 

# Instead we express the powers in terms of "x", the indeterminate in the # polynomial ring. F27pow = map(lift,F27star) F27pow 

alph = [chr(i) for i in range(65,91)]; alph 

correspondence = zip(alph,F27pow); correspondence