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 the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.