# 14 Non-Commutative Grobner Basis Methods

## 14.1 Non-Commutative Gröbner Bases

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