1,720,973 research outputs found
Context-Free Languages and Associative Algebras with Algebraic Hilbert Series
No full textIn this paper, homological methods together with the theory of formal languages of theoretical computer science are proved to be effective tools to determine the growth and the Hilbert series of an associative algebra. Namely, we construct a class of finitely presented associative algebras related to a family of context-free languages. This allows us to connect the Hilbert series of these algebras with the generating functions of such languages. In particular, we obtain a class of finitely presented graded algebras with non-rational algebraic Hilbert series
Stream/block ciphers, difference equations and algebraic attacks
Get PDFIn this paper we model a class of stream and block ciphers as systems of (ordinary) explicit difference equations over a finite field. We call this class “difference ciphers” and we show that ciphers of application interest, as for example systems of LFSRs with a combiner, TRIVIUM and KEELOQ, belong to the class. By using Difference Algebra, that is, the formal theory of difference equations, we can properly define and study important properties of these ciphers, such as their invertibility and periodicity. We describe then general cryptanalytic methods for difference ciphers that follow from these properties and are useful to assess the security. We illustrate such algebraic attacks in practice by means of the ciphers BIVIUM and KEELOQ
Computing noncommutative Hilbert series
No full textWe propose methods for computing the Hilbert series of multigraded right modules over the free associative algebra. In particular, we compute such series for noncommutative multigraded algebras. Using results from the theory of regular languages, we provide conditions when the methods are effective and hence the Hilbert series have a rational sum. Efficient variants of the methods are also developed for the truncations of infinite-dimensional algebras which provide approximations of possibly irrational Hilbert series. Moreover, we provide a characterization of the finite-dimensional algebras in terms of the nilpotency of a key matrix involved in the computations. Finally, we present a well-tested and complete implementation for the computation of graded and multigraded Hilbert series which has been developed in the kernel of the computer algebra system Singular (for the details, see preprint[1])
Koszul syzygies and sparse matrices for the computation of the Linear Strands
No full textIn the present paper some algorithms are proposed for computing Linear
Strands and Betti Numbers of graded modules over polynomial rings.
These algorithms are based on a block-decomposition, induced by the
Koszul syzygies, of the linear systems involved with the Hilbert’s method
for computing syzygies. Some further optimizations are suggested and
applied by the authors to an implementation they have developed of the
algorithms
Noncommutative algebras, context-free grammars and algebraic Hilbert series
Get PDFIn this paper we introduce a class of noncommutative (finitely generated) monomial algebras whose Hilbert series are algebraic functions. We use the concept of graded homology and the theory of unambiguous context-free grammars for this purpose. We also provide examples of finitely presented graded algebras whose corresponding leading monomial algebras belong to the proposed class and hence possess algebraic Hilbert series
A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium
Get PDFIn this paper we introduce a multistep generalization of the guess-and-determine or hybrid strategy for solving a system of multivariate polynomial equations over a finite field. In particular, we propose performing the exhaustive evaluation of a subset of variables stepwise, that is, by incrementing the size of such subset each time that an evaluation leads to a polynomial system which is possibly unfeasible to solve. The decision about which evaluation to extend is based on a preprocessing consisting in computing an incomplete Gröbner basis after the current evaluation, which possibly generates linear polynomials that are used to eliminate further variables. If the number of remaining variables in the system is deemed still too high, the evaluation is extended and the preprocessing is iterated. Otherwise, we solve the system by a complete Gröbner basis computation. Having in mind cryptanalytic applications, we present an implementation of this strategy in an algorithm called MULTISOLVE which is designed for polynomial systems having at most one solution. We prove explicit formulas for its complexity which are based on probability distributions that can be easily estimated by performing the proposed preprocessing on a testset of evaluations for different subsets of variables. We prove that an optimal complexity of MULTISOLVE is achieved by using a full multistep strategy with a maximum number of steps and in turn the standard guess-and-determine strategy, which essentially is a strategy consisting of a single step, is the worst choice. Finally, we extensively study the behaviour of MULTISOLVE when performing an algebraic attack on the well-known stream cipher TRIVIUM
On the regularity of the language of some T-ideals
No full textWe consider an algebra satisfying a polynomial identity (PI-algebra) and we define what the language generated by its T-ideal is. We conjecture the T-ideal of any PI-algebra is regular and in this paper we give results supporting the conjecture by computing the language of several classes of PI-algebras. Among them, we compute the language generated by some algebras of glued cells that are a useful tool to better understand the so-called Zariski-closed algebras
Action of the Borel group on monomial ideals
No full textLet T < GL_(n,K) be the Borel group of upper triangular matrices. In this paper we want to study the action of T on the set of monomial ideals of K[x_1,...,x_n] (K a field of characteristic zero) from a computational point of view. More specifically, we show that the stabilizer of a monomial ideal M < K[x_1,...,x_n] in T is a purely combinatorial object and we give an algorithm for computing it. Then we characterize the subgroups of T that are stabilizers of monomial ideals, we give an algorithm which finds if a given ideal J is in the orbit of a monomial ideal M under the action of T and in the affirmative case, finds the matrices W in T such that W * J = M. We show that the entries of W can be directly obtained from the coefficients of the generators of J, so in particular no solutions of polynomial equations are required
Super RSK-algorithms and super plactic monoid
No full textWe construct the analog of the plactic monoid for the super semistandard Young tableaux over a signed alphabet. This is done by developing a generalization of the Knuth's relations. Moreover we get generalizations of Greene's invariants and Young–Pieri rule. A generalization of the symmetry theorem in the signed case is also obtained. Except for this last result, all the other results are proved without restrictions on the orderings of the alphabets
- …
