49 research outputs found
Osservazioni sull'onomastica in alcune opere teatrali di Frisch, Fassbinder, Wiesel e Mitterer
No full textSeveral Jewish figures that appear in four contemporary theatre plays are interesting for diverse reasons and under different aspects. This onomastic investigation focuses on the works of the German Rainer Werner Fassbinder’s Der Müll, die Stadt und der Tod, the Swiss Max Frisch’s Andorra, the American Elie Wiesel’s Le procès de Shamgorod and the Austrian Felix Mitterer’s Kein schöner Land. The names of the – de facto or supposed – Jewish protagonists will be taken under examination, as well as other relevant anthroponyms and toponyms. Among some bizarre given and family names present in his play, Fassbinder doesn’t give a name to his Jewish character: his choice led to a huge controversy. Frisch’s Andri is not Jewish by birth, but those around him are convinced of that, and this aspect is reflected in his first name; not only Andorra, also the toponyms in Wiesel’s play deserve an examination. Finally, among the functions fulfilled by various names in Kein schöner Land, one choice the author makes draws our attention
Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations
No full textInternational audienceWe give a Las Vegas algorithm which computes the shifted Popov form of an nonsingular polynomial matrix of degree in expected field operations, where is theexponent of matrix multiplication and indicates that logarithmic factors are omitted. This is the first algorithm in for shifted row reduction with arbitraryshifts.Using partial linearization, we reduce the problem to the case where is the generic determinant bound, with bounded from above by both the average row degree and the average columndegree of the matrix. The cost above becomes , improving upon the cost of the fastest previouslyknown algorithm for row reduction, which is deterministic. Our algorithm first builds a system of modular equations whose solution set isthe row space of the input matrix, and then finds the basis in shifted Popovform of this set. We give a deterministic algorithm for this second stepsupporting arbitrary moduli in field operations, where is the number of unknowns and is the sumof the degrees of the moduli. This extends previous results with the same costbound in the specific cases of order basis computation and M-Pad\'eapproximation, in which the moduli are products of known linear factors
Bases de relations en une ou plusieurs variables : algorithmes rapides et applications
No full textIn this thesis, we study algorithms for a problem of finding relations in one or severalvariables. It generalizes that of computing a solution to a system of linear modularequations over a polynomial ring, including in particular the computation of Hermite-Padéapproximants and bivariate interpolants. Rather than a single solution, we aim atcomputing generators of the solution set which have good properties.Precisely, the input of our problem consists of a finite-dimensional module given bythe action of the variables on its elements, and of some elements of this module; the goalis to compute a Gröbner basis of the module of syzygies between these elements. In termsof linear algebra, the input describes a matrix with a type of Krylov structure, and thegoal is to compute a compact representation of a basis of the nullspace of this matrix.We propose several algorithms in accordance with the structure of the multiplicationmatrices which specify the action of the variables. In the case of a Jordan matrix, weaccelerate the computation of multivariate interpolants under degree constraints; ourresult for a Frobenius matrix leads to a faster algorithm for computing normal forms ofunivariate polynomial matrices. In the case of several dense matrices, we accelerate thechange of monomial order for Gröbner bases of multivariate zero-dimensional ideals.Dans cette thèse, nous étudions des algorithmes pour un problème de recherche de relationsà une ou plusieurs variables. Il généralise celui de calculer une solution à un systèmed’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple lecalcul d’approximants de Hermite-Padé ou d’interpolants bivariés. Plutôt qu’une seule solution,nous nous attacherons à calculer un ensemble de générateurs possédant de bonnespropriétés.Précisément, l’entrée de notre problème consiste en un module de dimension finiespécifié par l’action des variables sur ses éléments, et en un certain nombre d’élémentsde ce module ; il s’agit de calculer une base de Gröbner du module des relations entreces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structurede type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cettematrice.Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplicationqui représentent l’action des variables. Dans le cas d’une matrice de Jordan, nousaccélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultatspour une forme de Frobenius permettent d’accélérer le calcul de formes normalesde matrices polynomiales univariées. Enfin, dans le cas de plusieurs matrices denses,nous accélérons le changement d’ordre pour des bases de Gröbner d’idéaux multivariészéro-dimensionnels
Bases de relation en une ou plusieurs variables : algorithmes rapides et applications
No full textDans cette thèse, nous étudions des algorithmes pour un problème de recherche de relations à une ou plusieurs variables. Il généralise celui de calculer une solution à un système d’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple le calcul d’approximants de Hermite-Padé ou d’interpolants bivariés. Plutôt qu’une seule solution, nous nous attacherons à calculer un ensemble de générateurs possédant de bonnes propriétés. Précisément, l’entrée de notre problème consiste en un module de dimension finie spécifié par l’action des variables sur ses éléments, et en un certain nombre d’éléments de ce module ; il s’agit de calculer une base de Gröbner du modules des relations entre ces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structure de type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cette matrice. Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplication qui représentent l’action des variables. Dans le cas d’une matrice de Jordan,nous accélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultats pour une forme de Frobenius permettent d’accélérer le calcul de formes normales de matrices polynomiales univariées. Enfin, dans le cas de plusieurs matrices denses, nous accélérons le changement d’ordre pour des bases de Gröbner d’idéaux multivariés zéro-dimensionnels.In this thesis, we study algorithms for a problem of finding relations in one or several variables. It generalizes that of computing a solution to a system of linear modular equations over a polynomial ring, including in particular the computation of Hermite- Padéapproximants and bivariate interpolants. Rather than a single solution, we aim at computing generators of the solution set which have good properties. Precisely, the input of our problem consists of a finite-dimensional module given by the action of the variables on its elements, and of some elements of this module; the goal is to compute a Gröbner basis of the module of syzygies between these elements. In terms of linear algebra, the input describes a matrix with a type of Krylov structure, and the goal is to compute a compact representation of a basis of the nullspace of this matrix. We propose several algorithms in accordance with the structure of the multiplication matrices which specify the action of the variables. In the case of a Jordan matrix, we accelerate the computation of multivariate interpolants under degree constraints; our result for a Frobenius matrix leads to a faster algorithm for computing normal forms of univariate polynomial matrices. In the case of several dense matrices, we accelerate the change of monomial order for Gröbner bases of multivariate zero-dimensional ideals
Bases de relations en une ou plusieurs variables : algorithmes rapides et applications
No full textIn this thesis, we study algorithms for a problem of finding relations in one or severalvariables. It generalizes that of computing a solution to a system of linear modularequations over a polynomial ring, including in particular the computation of Hermite-Padéapproximants and bivariate interpolants. Rather than a single solution, we aim atcomputing generators of the solution set which have good properties.Precisely, the input of our problem consists of a finite-dimensional module given bythe action of the variables on its elements, and of some elements of this module; the goalis to compute a Gröbner basis of the module of syzygies between these elements. In termsof linear algebra, the input describes a matrix with a type of Krylov structure, and thegoal is to compute a compact representation of a basis of the nullspace of this matrix.We propose several algorithms in accordance with the structure of the multiplicationmatrices which specify the action of the variables. In the case of a Jordan matrix, weaccelerate the computation of multivariate interpolants under degree constraints; ourresult for a Frobenius matrix leads to a faster algorithm for computing normal forms ofunivariate polynomial matrices. In the case of several dense matrices, we accelerate thechange of monomial order for Gröbner bases of multivariate zero-dimensional ideals.Dans cette thèse, nous étudions des algorithmes pour un problème de recherche de relationsà une ou plusieurs variables. Il généralise celui de calculer une solution à un systèmed’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple lecalcul d’approximants de Hermite-Padé ou d’interpolants bivariés. Plutôt qu’une seule solution,nous nous attacherons à calculer un ensemble de générateurs possédant de bonnespropriétés.Précisément, l’entrée de notre problème consiste en un module de dimension finiespécifié par l’action des variables sur ses éléments, et en un certain nombre d’élémentsde ce module ; il s’agit de calculer une base de Gröbner du module des relations entreces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structurede type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cettematrice.Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplicationqui représentent l’action des variables. Dans le cas d’une matrice de Jordan, nousaccélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultatspour une forme de Frobenius permettent d’accélérer le calcul de formes normalesde matrices polynomiales univariées. Enfin, dans le cas de plusieurs matrices denses,nous accélérons le changement d’ordre pour des bases de Gröbner d’idéaux multivariészéro-dimensionnels
Certification of minimal approximant bases
No full textInternational audienceFor a given computational problem, a certificate is a piece of data that one(the prover) attaches to the output with the aim of allowing efficientverification (by the verifier) that this output is correct. Here, weconsider the minimal approximant basis problem, for which the fastest knownalgorithms output a polynomial matrix of dimensions and averagedegree using field operations. Wepropose a certificate which, for typical instances of the problem, iscomputed by the prover using additional fieldoperations and allows verification of the approximant basis by a Monte Carloalgorithm with cost bound . Besides theoretical interest, our motivation also comes from the fact thatapproximant bases arise in most of the fastest known algorithms for linearalgebra over the univariate polynomials; thus, this work may help indesigning certificates for other polynomial matrix computations.Furthermore, cryptographic challenges such as breaking records for discretelogarithm computations or for integer factorization rely in particular oncomputing minimal approximant bases for large instances: certificates canthen be used to provide reliable computation on outsourced and error-proneclusters
Cryptanalyse algébrique et contributions à la cryptographie post-quantique basée sur les codes correcteurs d’erreurs en métrique rang
No full textRank-based cryptography is a promising field of code-based cryptography where one uses the rank metric instead of the traditional Hamming metric. The Rank Decoding (RD) and the MinRank (MR) problems are at the core of rank-based cryptography ; for a few decades, combinatorial attacks were considered to be the most efficient to solve RD. In this thesis, we present algebraic attacks against RD and MR, namely MaxMinors and SupportMinors. The MaxMinors attack is far more efficient than combinatorial approches against RD, especially when the target rank to be decoded is in O(\sqrt(n)), the typical area for rank-based cryptosystems such as ROLLO and RQC. In this thesis, we also improve the Rank Quasi-Cyclic (RQC) encryption scheme, and propose two new schemes with competitive parameters. One of these schemes does not rely on the ideal structure, thus its security relies solely on decoding random codes when given several syndromes, that is the Rank Support Learning (RSL) problem. To study the complexity of these new schemes, we propose new attacks, both combinatorial and algebraic, against some important variants of the RD problem : Non-Homogeneous RD, RSL, and Non-Homogeneous RSL. We also present the cryptanalysis of the rank-based signature scheme RPS; and a reduction that yields new attacks against the PSSI problem which is at the core of Durandal, a rank-based signature scheme.Last but not least, we introduce a new difficult problem, namely the SquareSpace problem. We study its complexity, propose 4 challenges for the security level of 128 bits, and we design a signature scheme relying on the SquareSpace problem, together with its implementation in C.La cryptographie basée sur les codes correcteurs d'erreurs en métrique rang est un domaine prometteur de la cryptographie post-quantique, elle repose sur l'utilisation de la métrique rang au lieu de la métrique de Hamming. Le problème du décodage en métrique rang (RD) ainsi que le problème MinRank (MR) sont au cœur de la cryptographie basée sur les codes correcteurs d'erreurs en métrique rang. Pendant plusieurs décennies, les attaques combinatoires étaient considérées comme les plus efficaces pour attaquer RD ; dans cette thèse nous introduisons deux attaques contre RD et MR, que nous appelons respectivement MaxMinors et SupportMinors. Il s'avère que l'attaque MaxMinors est redoutablement plus efficace que les attaques combinatoires pour une zone de paramètres souvent utilisée en cryptographie basée sur les codes correcteurs d'erreurs en métrique rang, par exemple pour les cryptosystèmes ROLLO et RQC. Dans cette thèse, nous avons également amélioré le chiffrement Rank Quasi-Cyclic (RQC) en proposant deux nouvelles versions avec des paramètres compétitifs. Plus précisément, l'un de ces nouveaux schémas a l'avantage d'avoir une sécurité reposant uniquement sur le décodage de codes aléatoires en métrique rang avec plusieurs syndromes, c'est-à-dire sur le problème Rank Support Learning (RSL), variante de RD. Pour étudier la sécurité de ces deux nouveaux schémas, nous proposons plusieurs attaques, tant combinatoires qu'algébriques, contre des variantes de RD, à savoir Non-Homogeneous RD, RSL, and Non-Homogeneous RSL. Ensuite, nous présentons la cryptanalyse de la signature RPS, une signature basée sur les codes correcteurs d'erreurs en métrique rang. Dans cette thèse, nous donnons une réduction du problème PSSI vers MinRank. Le problème PSSI est au coeur du schéma de signature en métrique rang Durandal ; ainsi, cette réduction permet de bénéficier de nouvelles attaques contre ce problème. Enfin, nous concluons cette thèse en introduisant un nouveau problème difficile : SquareSpace. Nous étudions sa complexité en décrivant plusieurs attaques combinatoires et algébriques, avant de donner 4 challenges pour le niveau de sécurité 128 bits. Finalement, nous décrivons un schéma de signature dont la sécurité repose sur SquareSpace, ainsi que l'implémentation en C de ce schéma
A divide-and-conquer algorithm for computing Gröbner bases of syzygies in finite dimension
No full textInternational audienceLet be elements in a quotient which has finitedimension as a -vector space, where and is an-submodule of . We address the problem of computing a Gr\"obner basisof the module of syzygies of , that is, of vectors such that .An iterative algorithm for this problem was given by Marinari, M\"oller, andMora (1993) using a dual representation of as the kernel of acollection of linear functionals. Following this viewpoint, we design adivide-and-conquer algorithm, which can be interpreted as a generalization toseveral variables of Beckermann and Labahn's recursive approach for matrixPad\'e and rational interpolation problems. To highlight the interest of thismethod, we focus on the specific case of bivariate Pad\'e approximation andshow that it improves upon the best known complexity bounds
Computing syzygies in finite dimension using fast linear algebra
No full textInternational audienceWe consider the computation of syzygies of multivariate polynomials in a finite-dimensional setting: for a -module of finite dimension as a -vector space, and given elements in , the problem is to compute syzygies between the 's, that is, polynomials in such that in. Assuming that the multiplication matrices of the variables with respect to some basis of are known, we give an algorithm which computes the reduced Gr\"obner basis of the module of thesesyzygies, for any monomial order, using operations in the base field , where is the exponent of matrix multiplication. Furthermore, assuming that is itself given as , under some assumptions on we show that these multiplicationmatrices can be computed from a Gr\"obner basis of within thesame complexity bound. In particular, taking , and in, this yields a change of monomial order algorithm along thelines of the FGLM algorithm with a complexity bound which is sub-cubic in
Deterministic computation of the characteristic polynomial in the time of matrix multiplication
No full textInternational audienceThis paper describes an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, to our knowledge, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. Our algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form, and relies on new subroutines for transforming shifted reduced matrices into shifted weak Popov matrices, and shifted weak Popov matrices into shifted Popov matrices
