The RegularChains library in MAPLE
François Lemaire, Marc Moreno Maza, Yongjian Xie · ACM SIGSAM Bulletin · 2005
Performing calculations modulo a set of relations is a basic technique in algebra. For instance, computing the inverse of an integer modulo a prime integer or computing the inverse of the complex number 3 + 2t modulo the relation ℓ2 + 1 = 0. Computing modulo a set S containing more than one relation requires from S to have some mathematical structure. For instance, computing the inverse of p = x + y modulo S = {x2 + y + 1,y2 + x + 1} is difficult unless one realizes that this question is equivalent to computing the inverse of p modulo C = {x4 + 2x2 + x + 2,y + x2 + 1}. Indeed, from there one can simplify p using y = -x2 - 1 leading to q = -x2 + x - 1 and compute the inverse of q modulo x4 + 2x2 + x + 2 (using the extended Euclidean algorithm) leading to -1/2x3 - 1/2x. One commonly used mathematical structure for a set of algebraic relations is that of a Gröbner basis. It is particularly well suited for deciding whether a quantity is null or not modulo a set of relations. For inverse computations, the notion of a regular chain is more adequate. For instance, computing the inverse of p = x + y modulo the set C = {y2 - 2x + 1,x2 - 3x + 2}, which is both a Gröbner basis and a regular chain, is easily answered in this latter point of view. Indeed, it naturally leads to consider the GCD of p and Cy = y2 - 2x + 1 modulo the relation Cx = x2 - 3x + 2 = 0, which is [EQUATION] This shows that p has no inverse if x = 1 and has an inverse (which can be computed and which is -y + 2) if x = 2.