Involutive method for computing Gröbner bases over % MathType!MTEF!2!1!+- % feaagaart1ev2aaatCvAUfKttLearuqr1ngBPrgarmWu51MyVXgatC % vAUfeBSjuyZL2yd9gzLbvyNv2CaeHbd9wDYLwzYbItLDharyavP1wz % ZbItLDhis9wBH5garqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbb % L8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs0-yqaqpe % pae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaaiaabeqaam % aaeaqbaaGcbaWefv3ySLgznfgDOjdarCqr1ngBPrginfgDObcv39ga % iyaacqWFfcVrdaWgaaWcbaGaeGOmaidabeaaaaa!47CE! $$ \mathbb{F}_2 $$

Autor: Vladimir P. Gerdt, M. V. Zinin
Rok vydání: 2008
Předmět:
Zdroj: Programming and Computer Software. 34:191-203
ISSN: 1608-3261
0361-7688
DOI: 10.1134/s0361768808040026
Popis: In this paper, an involutive algorithm for computation of Grobner bases for polynomial ideals in a ring of polynomials in many variables over the finite field $$ \mathbb{F}_2 $$ with the values of variables belonging of $$ \mathbb{F}_2 $$ is considered. The algorithm uses Janet division and is specialized for a graded reverse lexicographical order of monomials. We compare efficiency of this algorithm and its implementation in C++ with that of the Buchberger algorithm, as well as with the algorithms of computation of Grobner bases that are built in the computer algebra systems Singular and CoCoA and in the FGb library for Maple. For the sake of comparison, we took widely used examples of computation of Grobner bases over ? and adapted them for $$ \mathbb{F}_2 $$ . Polynomial systems over $$ \mathbb{F}_2 $$ with the values of variables in $$ \mathbb{F}_2 $$ are of interest, in particular, for modeling quantum computation and a number of cryptanalysis problems.
Databáze: OpenAIRE
Externí odkaz: