检索结果-内蒙古大学图书馆

In-depth comparison of the Berlekamp-Massey-Sakata and the Scalar-FGLM algorithms: The adaptive variants

JOURNAL OF SYMBOLIC COMPUTATION 2020年 101卷 270-303页

作者： Berthomieu, Jeremy Faugere, Jean-Charles Sorbonne Univ CNRS INRIA LIP6Equipe PolSys F-75005 Paris France CryptoNext Secur Paris France

The BERLEKAMP-MASSEY-SAKATA algorithm and the SCALAR-FGLM algorithm both compute the ideal of relations of a multidimensional linear recurrent sequence. Whenever quering a single sequence element is prohibitive, the bottleneck of these algorithms becomes the computation of all the needed sequence terms. As such, having adaptive variants of these algorithms, reducing the number of sequence queries, becomes mandatory. A native adaptive variant of the SCALAR-FGLM algorithm was presented by its authors, the so-called Adaptive SCALAR-FGLM algorithm. In this paper, our first contribution is to make the BERLEKAMP MASSEY-SAKATA algorithm more efficient by making it adaptive to avoid some useless relation testings. This variant allows us to divide by four in dimension 2 and by seven in dimension 3 the number of basic operations performed on some sequence family. Then, we compare the two adaptive algorithms. We show that their behaviors differ in a way that it is not possible to tweak one of the algorithms in order to mimic exactly the behavior of the other. We detail precisely the differences and the similarities of both algorithms and conclude that in general the ADAPTIVE SCALAR-FGLM algorithm needs fewer queries and performs fewer basic operations than the Adaptive BERLEKAMP-MASSEY-SAKATA algorithm. We also show that these variants are always more efficient than the original algorithms. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： the bms algorithm The SCALAR-FGLM algorithm Grobner basis computation Multidimensional linear recurrent sequence algorithms comparison

来源：评论

学校读者我要写书评

暂无评论

Linear algebra for computing Grobner bases of linear recursive multidimensional sequences

引用

JOURNAL OF SYMBOLIC COMPUTATION 2017年 83卷 36-67页

作者： Berthomieu, Jeremy Boyer, Brice Faugere, Jean-Charles UPMC Univ Paris 06 Sorbonne Univ CNRS INRIALIP6Equipe PolSys 4 Pl Jussieu F-75252 Paris 05 France

The so-called Berlekamp-Massey-Sakata algorithm computes a Grobner basis of a 0-dimensional ideal of relations satisfied by an input table. It extends the Berlekamp-Massey algorithm to n-dimensional tables, for n > 1. We investigate this problem and design several algorithms for computing such a Grobner basis of an ideal of relations using linear algebra techniques. The first one performs a lot of table queries and is analogous to a change of variables on the ideal of relations. As each query to the table can be expensive, we design a second algorithm requiring fewer queries, in general. This FGLM-like algorithm allows us to compute the relations of the table by extracting a full rank submatrix of a multi-Hankel matrix (a multivariate generalization of Hankel matrices). Under some additional assumptions, we make a third, adaptive, algorithm and reduce further the number of table queries. Then, we relate the number of queries of this third algorithm to the geometry of the final staircase and we show that it is essentially linear in the size of the output when the staircase is convex. As a direct application to this, we decode n-cyclic codes, a generalization in dimension n of Reed Solomon codes. We show that the multi-Hankel matrices are heavily structured when using the LEX ordering and that we can speed up the computations using fast algorithms for quasi-Hankel matrices. Finally, we design algorithms for computing the generating series of a linear recursive table. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： the bms algorithm The FGLM algorithm Grobner basis computation 0-dimensional ideal Multidimensional linear recursive sequence

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：