Since we encountered some problems when we tried to use commutative polynomials for constructing secure Gröbner basis cryptosystems, it is natural to examine the possibility to use non-commutative algebraic structures. Given a finite set of letters X = {x_{1},…, x_{n}}, a word in X is an element of the form w = x_{t} x_{t} · x_{jt} with ij ϵ {1,…, n}. Here we denote the empty word by 1 and the set of all words by (X}. It is clear that concatenation makes (X} into a monoid with neutral element 1. We call it the free monoid on X.

Definition 14.1.1. Let K be a field and X = {x_{1},…,x_{n}}. The K-vector space with basis (X} can be made into a K-algebra by extending the multiplication of words ...

Start Free Trial

No credit card required