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 = {x1,…, xn}, a word in X is an element of the form w = xt xt · xjt 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 = {x1,…,xn}. The K-vector space with basis (X} can be made into a K-algebra by extending the multiplication of words ...

Get A Course in Mathematical Cryptography now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.