zbMATH — the first resource for mathematics

The implementation and complexity analysis of the branch Gröbner bases algorithm over Boolean polynomial rings. (English) Zbl 1352.68302
Feng, Ruyong (ed.) et al., Computer mathematics. 9th Asian symposium, ASCM 2009, Fukuoka, Japan, December 14–17, 2009, 10th Asian symposium, ASCM 2012, Beijing, China, October 26–28, 2012. Contributed papers and invited talks. Berlin: Springer (ISBN 978-3-662-43798-8/hbk; 978-3-662-43799-5/ebook). 157-169 (2014).
Summary: A new branch of Gröbner basis algorithm over Boolean ring has been presented in an earlier paper. In this paper, the detailed implementation and a rough complexity analysis is given. The branch Gröbner basis algorithm implements a variation of the F5 algorithm and bases on the ZDD data structure, which is also the data structure of the framework PolyBoRi. This branch Gröbner basis algorithm is mainly used to solve algebraic systems and attack multivariable cryptosystems, and its goal is to lower the complexity in each branch and expect better total complexity. An important proposition ensures the two original criteria of the non-branch F5 algorithm could still reject almost all unnecessary computations in this new branch algorithm. The timings show this branch algorithm performs very well for randomly generated systems as well as a class of stream ciphers which is generated by the linear feedback shift register (LFSR).
For the entire collection see [Zbl 1309.68008].
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W40 Analysis of algorithms
94A60 Cryptography
FGb; PolyBoRi
Full Text: DOI