To see the other types of publications on this topic, follow the link: Base du Gröbner.
Dissertations / Theses on the topic 'Base du Gröbner'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Base du Gröbner.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Amendola, Teresa. "Basi di Gröbner e anelli polinomiali." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amslaurea.unibo.it/19458/.
Full textAbstract:
In questo elaborato ci proponiamo di fornire alcuni strumenti utili per illustrare il collegamento tra varietà affini e ideali polinomiali. La tesi segue l'approccio computazionale e sfrutta quindi alcuni algoritmi per la dimostrazione dei risultati principali. Si prova il Teorema della Base di Hilbert e si introducono le basi di Gröbner per la dimostrazione del Nullstellensatz.
2
Vilanova, Fábio Fontes. "Sistemas de equações polinomiais e base de Gröbner." Universidade Federal de Sergipe, 2015. https://ri.ufs.br/handle/riufs/6524.
Full textAbstract:
The main objective of this dissertation is to present an algebraic method capable of determining a solution, if any, of a non linear polynomial equation systems using Gröbner basis. In order to accomplish that, we first present some concepts and theorems linked to polynomial rings with several undetermined and monomial
ideals where we highlight the division extended algorithm, the Hilbert Basis and the Buchberger´s algorithm. Beyond that, using basics of Elimination and Extension Theorems, we present an algebraic solution to the map coloring that use 3 colors as
well as a general solution to the Sudoku puzzle.O objetivo principal desse trabalho é, usando bases de Gröbner, apresentar um método algébrico capaz de determinar a solução, quando existir, de sistemas de equações polinomiais não necessariamente lineares. Para tanto, necessitamos inicialmente apresentar alguns conceitos e teoremas ligados a anéis de polinômios com várias indeterminadas e de ideais monomiais, dentre os quais destacamos o algoritmo extendido da divisão, o teorema da Base de Hilbert e o algoritmo de Buchberger. Além disso, usando noções básicas da Teoria de eliminação e extensão, apresentamos uma solução algébrica para o problema da coloração de mapas usando três cores, bem como um solução geral para o puzzle Sudoku.
3
Hashemi, Amir. "Structure et compléxité des bases de Gröbner." Paris 6, 2006. http://www.theses.fr/2006PA066116.
Full text
4
Bender, Matias Rafael. "Algorithms for sparse polynomial systems : Gröbner bases and resultants." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS029.
Full textAbstract:
La résolution de systèmes polynomiaux est l’un des problèmes les plus anciens et importants en mathématiques informatiques et a des applications dans plusieurs domaines des sciences et de l’ingénierie. C'est un problème intrinsèquement difficile avec une complexité au moins exponentielle du nombre de variables. Cependant, dans la plupart des cas, les systèmes polynomiaux issus d'applications ont une structure quelconque. Dans cette thèse, nous nous concentrons sur l'exploitation de la structure liée à la faible densité des supports des polynômes; c'est-à-dire que nous exploitons le fait que les polynômes n'ont que quelques monômes à coefficients non nuls. Notre objectif est de résoudre les systèmes plus rapidement que les estimations les plus défavorables, qui supposent que tous les termes sont présents. Nous disons qu'un système creux est non mixte si tous ses polynômes ont le même polytope de Newton, et mixte autrement. La plupart des travaux sur la résolution de systèmes creux concernent le cas non mixte, à l'exception des résultants creux et des méthodes d'homotopie. Nous développons des algorithmes pour des systèmes mixtes. Nous utilisons les résultantes creux et les bases de Groebner. Nous travaillons sur chaque théorie indépendamment, mais nous les combinons également: nous tirons parti des propriétés algébriques des systèmes associés à une résultante non nulle pour améliorer la complexité du calcul de leurs bases de Groebner; par exemple, nous exploitons l’exactitude du complexe de Koszul pour déduire un critère d’arrêt précoce et éviter tout les réductions à zéro. De plus, nous développons des algorithmes quasi-optimaux pour décomposer des formes binairesSolving polynomial systems is one of the oldest and most important problems in computational mathematics and has many applications in several domains of science and engineering. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. In this thesis we focus on exploiting the structure related to the sparsity of the supports of the polynomials; that is, we exploit the fact that the polynomials only have a few monomials with non-zero coefficients. Our objective is to solve the systems faster than the worst case estimates that assume that all the terms are present. We say that a sparse system is unmixed if all its polynomials have the same Newton polytope, and mixed otherwise. Most of the work on solving sparse systems concern the unmixed case, with the exceptions of mixed sparse resultants and homotopy methods. In this thesis, we develop algorithms for mixed systems. We use two prominent tools in nonlinear algebra: sparse resultants and Groebner bases. We work on each theory independently, but we also combine them to introduce new algorithms: we take advantage of the algebraic properties of the systems associated to a non-vanishing resultant to improve the complexity of computing their Groebner bases; for example, we exploit the exactness of some strands of the associated Koszul complex to deduce an early stopping criterion for our Groebner bases algorithms and to avoid every redundant computation (reductions to zero). In addition, we introduce quasi-optimal algorithms to decompose binary forms
5
Rahmany, Sajjad. "Utilisation des bases de Gröbner SAGBI pour la résolution des systèmes polynômiaux invariants par symétries." Paris 6, 2009. http://www.theses.fr/2009PA066214.
Full textAbstract:
Dans cette thèse, nous proposons une méthode efficace pour résoudre des systèmes polynômiaux dont les équations sont invariantes par l'action d'un groupe fini G. L'idée est calculer simultanément une base de Gröbner SAGBI(une génération des bases de Gröbner à des idéaux de sous algèbres de l'anneau des polynômes) et une base de Gröbner dans l'anneau des invariants symétriques. Plus précisément, nous proposons dans cette thèse deux algorithmes: nous explicitions d'abord un algorithme à la F5 pour calculer efficacement une base de Gröbner SAGBI. Le deuxième algorithme est une version légèrement modifiée de l'algorithme FGLM qui permet de convertir une base de Gröbner SAGBI tronquée d'un idéal de dimension zéro en une base de Gröbner tronquée dans l'anneau des invariants symétriques. Enfin, nous montrons comment ces algorithmes peuvent être combinés pour trouver les racines complexes d'un tel système algébrique.
6
Rocha, Junior Mauro Rodrigues. "Bases de Gröbner aplicadas a códigos corretores de erros." Universidade Federal de Juiz de Fora (UFJF), 2017. https://repositorio.ufjf.br/jspui/handle/ufjf/5946.
Full textAbstract:
Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-11-06T18:45:09Z
No. of bitstreams: 1
maurorodriguesrochajunior.pdf: 550118 bytes, checksum: 5b26ad1ab2bd9d4a190d742762346968 (MD5)Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-11-09T14:32:38Z (GMT) No. of bitstreams: 1 maurorodriguesrochajunior.pdf: 550118 bytes, checksum: 5b26ad1ab2bd9d4a190d742762346968 (MD5)
Made available in DSpace on 2017-11-09T14:32:38Z (GMT). No. of bitstreams: 1 maurorodriguesrochajunior.pdf: 550118 bytes, checksum: 5b26ad1ab2bd9d4a190d742762346968 (MD5) Previous issue date: 2017-08-11
O principal objetivo desse trabalho é estudar duas aplicações distintas das bases de Gröbner a códigos lineares. Com esse objetivo, estudamos como relacionar códigos a outras estruturas matemáticas, fazendo com que tenhamos novas ferramentas para a realização da codificação. Em especial, estudamos códigos cartesianos afins e os códigos algébrico-geométricos de Goppa.
The main objective of this work is to study two different applications of Gröbner basis to linear codes. With this purpose, we study how to relate codes to other mathematical structures, allowing us to use new tools to do the coding. In particular, we study affine cartesian codes e algebraic-geometric Goppa codes.
7
Sénéchaud, Pascale. "Calcul formel et parallélisme : bases de Gröbner booléennes, méthodes de calcul : applications, parallélisation." Grenoble INPG, 1990. http://tel.archives-ouvertes.fr/tel-00337227.
Full textAbstract:
Nous présentons les bases de Grobner, leur utilisation et la parallélisation des algorithmes qui les calculent dans le cas de polynômes booléens. Une première partie est consacrée à la présentation théorique des bases de Grobner dans le cas général. Cette présentation se veut accessible a des non-spécialistes. Une étude bibliographique de la complexité est faite. Une deuxième partie concerne les applications des bases de Grobner booléennes en calcul propositionnel et en preuve de circuits combinatoires. Nous proposons un algorithme de preuve formelle de circuits combinatoires hiérarchisés. Dans la troisième partie nous adaptons l'algorithme séquentiel au cas booléen et nous étudions plus en détail la normalisation. Nous proposons deux méthodes de parallélisation a granularité différentes. Nous analysons et comparons plusieurs implantations parallèles et présentons des résultats expérimentaux. Les algorithmes sont généralisables au cas des polynômes a coefficients rationnels. Nous soulignons l'influence de la répartition des données sur le temps d'exécution. Nous présentons une methode de répartition des polynômes basée sur la recherche de chemins de longueur donnée dans un graphe oriente. Cette répartition nous permet d'obtenir des résultats interpretables et de conclure sur les différents algorithmes
8
García, Fontán Jorge. "Singularity and Stability Analysis of vision-based controllers." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS015.
Full textAbstract:
L’objectif de cette thèse doctoral est d’explorer les cas d’échec de l’asservissement visuel, d’un point de vue mathématique rigoureux et à l’aide d’outils de calcul exact issus de la géométrie algébrique et du calcul formel. Les cas d’échec possibles proviennent de deux sources : les singularités des équations cinématiques, et l’existence de multiples points d’équilibre, ce qui affecte la stabilité asymptotique globale des lois de contrôle. Dans cette thèse, nous avons atteint deux objectifs principaux. Le premier est de calculer les conditions de singularité pour le modèle d’interaction lié à l’observation de plus de trois droites 3D, en étendant les résultats des publications antérieurs pour trois droites. Le deuxième est le calcul des points critiques en IBVS dans l’observation de quatre points de référence, comme première étape vers l’analyse de la stabilité globale des méthodes d’asservissement visuelThe objective of this PhD thesis is to explore the failure cases of Image-Based Visual Servoing (IBVS), a class of Robotics controllers based on computer vision data. The failure cases arise from two sources: the singularities of the governing kinematic equations, and the existance of multiple stable points of equilibrium, which impacts the global asymptotic stability of the control laws. In this thesis, we study these two problems from a rigurous mathematical perspective and with the help of exact computational tools from algebraic geometry and computer algebra. Two main objectives were achieved. The first is to determine the conditions for singularity for the interaction model related to the observation of more than three straight lines in space, which extends the previous existing results for three lines. The second is the computation of the critical points (the equilibrium points) of IBVS in the observation of four reference points, as a first step towards an analysis of the global stability behaviour of visual servoing
9
Chakraborty, Olive. "Design and Cryptanalysis of Post-Quantum Cryptosystems." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS283.
Full textAbstract:
La résolution de systèmes polynomiaux est l’un des problèmes les plus anciens et des plus importants en Calcul Formel et a de nombreuses applications. C’est un problème intrinsèquement difficile avec une complexité, en générale, au moins exponentielle en le nombre de variables. Dans cette thèse, nous nous concentrons sur des schémas cryptographiques basés sur la difficulté de ce problème. Cependant, les systèmes polynomiaux provenant d’applications telles que la cryptographie multivariée, ont souvent une structure additionnelle cachée. En particulier, nous donnons la première cryptanalyse connue du crypto-système « Extension Field Cancellation ». Nous travaillons sur le schéma à partir de deux aspects, d’abord nous montrons que les paramètres de challenge ne satisfont pas les 80bits de sécurité revendiqués en utilisant les techniques de base Gröbner pour résoudre le système algébrique sous-jacent. Deuxièmement, en utilisant la structure des clés publiques, nous développons une nouvelle technique pour montrer que même en modifiant les paramètres du schéma, le schéma reste vulnérable aux attaques permettant de retrouver le secret. Nous montrons que la variante avec erreurs du problème de résolution d’un système d’équations est encore difficile à résoudre. Enfin, en utilisant ce nouveau problème pour concevoir un nouveau schéma multivarié d’échange de clés nous présentons un candidat qui a été soumis à la compétition Post-Quantique du NISTPolynomial system solving is one of the oldest and most important problems incomputational mathematics and has many applications in computer science. Itis intrinsically a hard problem with complexity at least single exponential in the number of variables. In this thesis, we focus on cryptographic schemes based on the hardness of this problem. In particular, we give the first known cryptanalysis of the Extension Field Cancellation cryptosystem. We work on the scheme from two aspects, first we show that the challenge parameters don’t satisfy the 80 bits of security claimed by using Gröbner basis techniques to solve the underlying algebraic system. Secondly, using the structure of the public keys, we develop a new technique to show that even altering the parameters of the scheme still keeps the scheme vulnerable to attacks for recovering the hidden secret. We show that noisy variant of the problem of solving a system of equations is still hard to solve. Finally, using this new problem to design a new multivariate key-exchange scheme as a candidate for NIST Post Quantum Cryptographic Standards
10
Thomas, Gabriel. "Contributions théoriques et algorithmiques à l'étude des équations différencielles-algébriques : Approche par le calcul formel." Grenoble INPG, 1997. http://www.theses.fr/1997INPG0095.
Full textAbstract:
Cette thèse de Calcul Formel présente une étude des Equations Différentielles-Algébriques (ou avec contraintes), de type polynomiales et quasilinéaires. Il faut en général dériver ces équations pour pouvoir décider de l'existence de solutions. Ce nombre de dérivations est appelé indice par les numériciens. La première partie précise la définition de l'indice, par une approche algébrique du problème, qui est ensuite comparée aux travaux récents en algèbre différentielle, théorie créée par J. F. Ritt vers 1940. Nous montrons que l'indice ne dépend que des composantes irréductibles de la variété des contraintes. L'utilisation d'idéaux premiers rend ces résultats peu effectifs. En deuxième partie nous remédions à ce problème en utilisant un algorithme dû à D. Lazard, qui décompose les EDA en systèmes triangulaires. Les variétés sont représentées par des idéaux radicaux équidimensionnels. L'algorithme est implémenté dans les systèmes Maple V et GB, pour les calculs de bases de Gröbner. Il s'agit du premier algorithme entièrement formel calculant indice et ensemble des contraintes d'une EDA. La dernière partie étudie localement les points-impasse des EDO implicites, singularités génériques des EDA quasi-linéaires. En nous plaçant dans l'espace complexe, nous montrons simplement que ces points ne sont autres que des points de branchement algébriques des solutions. L'exposant des séries de Puiseux solutions en ces points est obtenu en considérant leur multiplicité dans le déterminant du système, ce qui généralise un résultat de Briot et BouquetIn this Computer Algebra thesis we develop the thoery of quasi-linear Differential-Algebraic Equations (DAEs) with polynomial coefficients. The existence of solutions to these systems is answered after differentiating the equations ; the minimal number of differentiations to get an integrable form is called the differential index by numerical analysts. In the first part, we make precise the definition of the differential index. By use of algebraic geometry and commutative algebra (modules over quotient rings) we show that the index depends on the irreducible components of the constraints variety of the original DAEs. The second part is devoted to algorithmic issues : we give an original and effective method of decomposing a quasi-linear polynomial DAEs into ODEs on equidimensional algebraic sets. For each subsystem, the index is computed, while both algebraic and differential parts are obtained without using the factorization of polynomials. This algorithm has been implemented with Maple and GB software. The other part of the thesis deals with the local study of so-called impasse points of non linear Differential Equations. These points are the standard singularities of quasi-linear DAEs. Taking a complex viewpoint, we show by simple calculations that impasse points are actually algebraic branch points of the soluions. Getting the multiplicity of these branch points from the determinant of the differential part, we show how to express the solution as a Puiseux expansion near a given impasse point
11
Liang, Ye. "Approximate Gröbner basis." Paris 6, 2011. http://www.theses.fr/2011PA066034.
Full textAbstract:
Résumé La méthode des bases de Gröbner est un outil important pour résoudre des équations polynômes. Lorsque nous travaillons avec des grands systèmes qui consistent de polynômes avec des coefficients de nombres entiers, les algorithmes exacts existants sont habituellement des CPU- intensif et de la mémoire-intensive. Les demandes pour d’un rendement plus élevé et d’un coût de mémoire plus bas exigent des calculs numériques utilisant des nombres à virgule flottante. Cependant, il a été souvent dit dans plusieurs littératures que le calcul numérique des bases de Gröbner est fortement instable. Dans cette thèse, le problème des instabilités est étudié par l’intermédiaire d’une série de techniques en choisissant des longueurs appropriées de nombres à virgule flottante, de tracer les pertes de précision de coefficients dans les polynômes, d’identifier les zéros, et de pivoter des principaux monômes de polynômes. En outre, nous avons implanté une théorie pour le phénomène de la discontinuité artificielle dans un cas simple-paramétrique. Nous avons mis en application nos algorithmes à l’intérieur de Maple13 avec ces techniques pour calculer les bases approximatives de Gröbner. Les expériences démontrent que les algorithmes peuvent traiter les systèmes polynômes indécis, bien que nos implémentations aient de grand espace pour être optimiser.
12
Chaussade, Lionel. "Codes correcteurs avec les polynômes tordus." Phd thesis, Université Rennes 1, 2010. http://tel.archives-ouvertes.fr/tel-00813705.
Full textAbstract:
Les anneaux de polynômes sont l'un des outils privilégiés pour construire et étudier des familles de codes correcteurs. Nous nous proposons, dans cette thèse, d'utiliser des anneaux de Öre, qui sont des anneaux de polynômes non-commutatifs, afin de créer des codes correcteurs. Cette approche nous permet d'obtenir des familles de codes correcteurs plus larges que si l'on se restreint au cas commutatif mais qui conservent de nombreuses propriétés communes. Nous obtenons notamment un algorithme qui permet de fabriquer des codes correcteurs dont la distance de Hamming ou la distance rang est prescrite. C'est ainsi que nous avons exhibé deux codes qui améliorent la meilleure distance minimale connue pour un code de même longueur et de même dimension. L'un est de paramètres $[42,14,21]$ sur le corps $\mathbb{F}_8$ et l'autre de paramètres $[40,23,10]$ sur $\mathbb{F}_4$. La généralisation de cette étude au cas d'anneaux polynomiaux multivariés est également présentée; l'outil principal est alors la théorie des bases de Gröbner qui s'adapte dans ce cadre non-commutatif et permet de manipuler des idéaux pour créer de nouvelles familles de codes correcteurs.
13
Apel, Joachim. "Effective Gröbner Structures." Universität Leipzig, 1997. https://ul.qucosa.de/id/qucosa%3A34542.
Full textAbstract:
Since Buchberger intrduced the theory of Gröbner bases in 1965 it has become one of the most important tools in constructive algebra and, nowadays, it is the kernel of many algorithms in the theory of polynomial ideals and algebraic geometry. Motivated by the results in polynomial rings there have been investigeated al lot of possibilities to generalise Buchberger's ideas to other types of rings. The perhaps most general concept, though it does not cover all extensions reported in the literature, is the extension to graded structures due to Robbiano and Mora. But in order to obtain algorithmic solutions for the compution of Gröbner bases it needs additional computability assumptions. The subject of this paper is the presentation of some classes of effective graded structures.
14
Zhao, Yonggan. "Gröbner Bases and Syzygy Modules." TopSCHOLAR®, 1995. http://digitalcommons.wku.edu/theses/924.
Full textAbstract:
The theory of Gröbner bases has become a useful tool in computational commutative algebra. In this paper, we outline some basic results, as they are found in [1], including the concepts of terms ordering, multivariable polynomial division, Gröbner bases, Buchberger's algorithm, and syzygy modules. Specially, we present several equivalent definitions for Gröbner bases and prove how to compute a Gröbner basis for an ideal I of A = k[x1, x2, • • • , xn] generated by {fl, f2, • • • , f8} through Buchberger's algorithm. As an application of Gröbner bases, we present a standard method (see [1]) to compute the syzygy module of a set {f1, f2, • • • , f8} of polynomials, illustrated with original examples. Finally, we implement these examples on the computer using the Mathematica package of [4].
15
Huot, Louise. "Résolution de systèmes polynomiaux et cryptologie sur les courbes elliptiques." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2013. http://tel.archives-ouvertes.fr/tel-00925271.
Full textAbstract:
Depuis ces dix dernières années, les attaques sur le logarithme discret sur les courbes elliptiques (ECDLP) mettant en jeu la résolution de systèmes polynomiaux connaissent un large succès. C'est dans ce contexte que s'inscrit cette thèse dont les contributions sont doubles. D'une part, nous présentons de nouveaux outils de résolution de systèmes polynomiaux par bases de Gröbner. Nous montrons que la résolution de systèmes avec symétries est étroitement liée à la résolution de systèmes quasi-homogènes. Nous proposons ainsi de nouveaux résultats de complexité pour la résolution de tels systèmes. Nous nous intéressons également à l'étape bloquante de la résolution de systèmes : le changement d'ordre pour bases de Gröbner. La complexité classique de cette étape est cubique en le nombre de solutions et domine la complexité totale de la résolution. Nous proposons pour la première fois des algorithmes de changement d'ordre de complexité sous-cubique en le nombre de solutions. D'autre part, nous nous intéressons à l'attaque du logarithme discret sur les courbes elliptiques par calcul d'indice proposée par Gaudry. Nous mettons en évidence des familles de courbes elliptiques possédant des symétries particulières. Ces symétries impliquent un gain exponentiel sur la complexité de la résolution du ECDLP. Nous obtenons ainsi de nouveaux paramètres de sécurité pour certaines instances du ECDLP. Une des étapes principales de cette attaque nécessite le calcul de polynômes de sommation introduits par Semaev. Les symétries des courbes elliptiques binaires nous permettent d'élaborer un nouvel algorithme par évaluation-interpolation pour le calcul des polynômes de sommation. Munis de cet algorithme nous établissons un nouveau record pour le calcul de ces polynômes.
16
Huot, Louise. "Résolution de systèmes polynomiaux et cryptologie sur les courbes elliptiques." Phd thesis, Paris 6, 2013. http://www.theses.fr/2013PA066709.
Full textAbstract:
Depuis ces dix dernières années, les attaques algébriques sur lelogarithme discret sur les courbes elliptiques (ECDLP) connaissent unlarge succès. C'est dans ce contexte que s'inscrit cette thèse dontles enjeux sont doubles. D'une part, nous présentons de nouveaux outils de cryptanalysealgébrique c'est à dire de nouveaux algorithmes de résolution desystèmes polynomiaux. Dans un premier temps, nous étudions lessystèmes avec symétries. Nous montrons que la résolution de telssystèmes est étroitement liée à la résolution de systèmesquasi-homogènes et proposons ainsi de nouveaux résultats decomplexité. Dans un second temps, nous nous intéressons à l'étapebloquante de la résolution de systèmes par bases de Gröbner : lechangement d'ordre. La complexité classique de cette étape est cubiqueen le nombre de solutions. Nous proposons pour la première foisdes algorithmes de changement d'ordre de complexité sous-cubique en lenombre de solutions. D'autre part, nous étudions la résolution du problème de décompositionde points (PDP) sous-jacent aux attaques algébriques du ECDLP. Nousmettons en évidence des familles de courbes elliptiques possédant dessymétries particulières. Ces symétries impliquent un gain exponentielsur la complexité de la résolution du PDP. La modélisation du PDP sousforme de systèmes polynomiaux nécessite le calcul des polynômes deSemaev. Les symétries des courbes binaires nous permettent d'élaborerun nouvel algorithme par évaluation interpolation pour le calcul de cespolynômes. Muni de cet algorithme nous établissons unnouveau record de calcul de polynômes de SemaevSince the last decade, algebraic attacks on the elliptic curvediscrete logarithm problem (ECDLP) are successful. This thesis takesplace in this context and its main stakes are twofold. On the one hand, we present new tools for algebraic cryptanalysis thatis to say new algorithms for polynomial systems solving. First, weinvestigate polynomial systems with symetries. We show that solvingsuch a system is closely related to solve quasi-homogeneous systemsand thus we propose new complexity bounds. Then, we study thebottleneck of solving polynomial systems with Gröbner bases: change ofordering algorithms. The usual complexity for such algorithms is cubicin the number of solutions. For the first time, we propose new changeof ordering algorithms with sub-cubic complexity in the number ofsolutions. On the other hand, we investigate the point decomposition probleminvolved in algebraic attacks on the ECDLP. We highlight some familiesof elliptic curves that admit particular symmetries. These symmetriesimply an exponential gain on the complexity of solving the pointdecomposition problem. The modelling of this problem requires tocompute Semaev summation polynomials. The symmetries of binary curvesallow us to propose a new algorithm to compute summationpolynomials. Equipped with this algorithm we establish a new record onthe computation of these polynomials
17
Ødegård, Rune Steinsmo. "Hash Functions and Gröbner Bases Cryptanalysis." Doctoral thesis, Norges teknisk-naturvitenskapelige universitet, Institutt for telematikk, 2012. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-16445.
Full textAbstract:
Hash functions are being used as building blocks in such diverse primitives as commitment schemes, message authentication codes and digital signatures. These primitives have important applications by themselves, and they are also used in the construction of more complex protocols such as electronic voting systems, online auctions, public-key distribution, mutual authentication handshakes and more. Part of the work presented in this thesis has contributed to the \SHA-3 contest" for developing the new standard for hash functions organized by the National Institute of Standards and Technology. We constructed the candidate Edon-R, which is a hash function based on quasigroup string transformation. Edon-R was designed to be much more efficient than SHA-2 cryptographic hash functions, while at the same time offering same or better security. Most notably Edon-R was the most efficient hash function submitted to the contest. Another contribution to the contest was our cryptanalysis of the second round SHA-3 candidate Hamsi. In our work we studied Hamsi's resistance to differential and higher-order differential cryptanalysis, with focus on the 256-bit version of Hamsi. Our main results are efficient distinguishers and near-collisions for its full (3-round) compression function, and distinguishers for its full (6-round) finalization function, indicating that Hamsi's building blocks do not behave ideally. Another important part of this thesis is the application of Gröbner bases. In the last decade, Gröbner bases have shown to be a valuable tool for algebraic cryptanalysis. The idea is to set up a system of multivariate equations such that the solution of the system reveals some secret information of the cryptographic primitive. The system is then solved with Gröbner bases computation. Staying close to the topic of hash functions, we have applied this tool for cryptanalysis and construction of multivariate digital signature schemes, which is a major hash function application. The result of this is our cryptanalysis of the public-key cryptosystem MQQ, where we show exactly why the multivariate quadratic equation system is so easy to solve in practice. The knowledge we gained from finding the underlying weakness of the MQQ scheme was used to construct a digital signature scheme. The resulting scheme, MQQ-SIG, is a provably CMA resistant multivariate quadratic digital signature scheme based on multivariate quadratic quasigroups. The scheme is designed to be very fast both in hardware and in software. Compared to some other multivariate quadratic digital signature schemes, MQQ-SIG is much better in signing and private key size, while worse in key generation, verification and public key size. This means that MQQ-SIG is a good alternative for protocols where the constrained environment is on the side of the signer.
18
Lee, Wai Kei Peter. "Gröbner bases in rational homotopy theory." Thesis, Massachusetts Institute of Technology, 2008. http://hdl.handle.net/1721.1/43786.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2008.Includes bibliographical references (leaves 38-39).
The Mayer-Vietoris sequence in cohomology has an obvious Eckmann-Hilton dual that characterizes the homotopy of a pullback, but the Eilenberg-Moore spectral sequence has no dual that characterizes the homotopy of a pushout. The main obstacle is the lack of an Eckmann-Hilton dual to the Kiinneth theorem with which to understand the homotopy of a coproduct. This difficulty disappears when working rationally, and we dualize Rector's construction of the Eilenberg-Moore spectral sequence to produce a spectral sequence converging to the homotopy of a pushout. We use Gröbner-Shirshov bases, an analogue of Gröbner bases for free Lie algebras, to compute directly the E2 term for pushouts of wedges of spheres. In particular, for a cofiber sequence A --> X --> C where A and X are wedges of spheres, we use this calculations to generalize a result of Anick by giving necessary and sufficient conditions for the map X --> C to be surjective in rational homotopy. More importantly, we are able to avoid the use of differential graded algebra and minimal models, and instead approach simple but open problems in rational homotopy theory using a simplicial perspective and the combinatorial properties of Gröbner-Shirshov bases.
by Wai Kei Peter Lee.
Ph.D.
19
Cabarcas, Daniel. "Gröbner Bases Computation and Mutant Polynomials." University of Cincinnati / OhioLINK, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1307321300.
Full text
20
Rinaldi, Luca. "Codici ciclici e basi di Gröbner." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amslaurea.unibo.it/8714/.
Full textAbstract:
Richiamo di elementi di algebra, tra cui: polinomi, ordini monomiali e base di Gröbner per ideali e sottomoduli con anche algoritmo FGLM. Descrizione dei codici, dei codici lineari, codifica e decodifica, matrice generatrice, matrice forma standard, matrice di controllo parità, codici ciclici con corrispondenza con ideali e polinomi generatori. Codice Reed-Solomon caso particolare di codice ciclico. Codici ciclici m-dimensionali e codifica sistematica con basi di Gröbner. Algoritmo di decodifica per Reed-Solomon con soluzione chiave e utilizzando basi di Gröbner sui sottomoduli.
21
Gameiro, Simoes Bruno Manuel. "New Strategies for Computing Gröbner Bases." Doctoral thesis, Università degli studi di Trento, 2013. https://hdl.handle.net/11572/369198.
Full textAbstract:
Gröbner bases are special sets of polynomials, which are useful to solve problems in many fields such as computer vision, geometric modeling, geometric theorem proving, optimization, control theory, statistics, communications, biology, robotics, coding theory, and cryptography.
The major disadvantage of algorithms to compute Gröbner bases is that computations can use a lot of computer power. One of the reasons is the amount of useless critical pairs that the algorithm has to compute. Hence, a lot of effort has been put into developing new criteria to detect such pairs in advance.
This thesis is devoted to describe efficient algorithms for the computation of Gröbner bases, with particular emphasis to those based on polynomial signatures. The idea of associating each polynomial with a signature on which the criteria and reduction steps depend, has become extremely popular in part due to its good performance.
Our main result combines the criteria from Gao-Volny-Wang's algorithm with the knowledge of Hilbert Series. A parallel implementation of the algorithm is also investigated to improve the computational efficiency. Our algorithm is implemented in CoCoALib, a C++ free library for computations in commutative algebra.
22
Gameiro, Simões Bruno Manuel. "New Strategies for Computing Gröbner Bases." Doctoral thesis, University of Trento, 2013. http://eprints-phd.biblio.unitn.it/940/1/thesis.pdf.
Full textAbstract:
Gröbner bases are special sets of polynomials, which are useful to solve problems in many fields such as computer vision, geometric modeling, geometric theorem proving, optimization, control theory, statistics, communications, biology, robotics, coding theory, and cryptography.
The major disadvantage of algorithms to compute Gröbner bases is that computations can use a lot of computer power. One of the reasons is the amount of useless critical pairs that the algorithm has to compute. Hence, a lot of effort has been put into developing new criteria to detect such pairs in advance.
This thesis is devoted to describe efficient algorithms for the computation of Gröbner bases, with particular emphasis to those based on polynomial signatures. The idea of associating each polynomial with a signature on which the criteria and reduction steps depend, has become extremely popular in part due to its good performance.
Our main result combines the criteria from Gao-Volny-Wang's algorithm with the knowledge of Hilbert Series. A parallel implementation of the algorithm is also investigated to improve the computational efficiency. Our algorithm is implemented in CoCoALib, a C++ free library for computations in commutative algebra.
23
Ge, Wenfeng. "Gröbner Bases Theory and The Diamond Lemma." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/2951.
Full textAbstract:
Commutative Gröbner bases theory is well known and widely used. In this thesis, we will discuss thoroughly its generalization to noncommutative polynomial ring k<X> which is also an associative free algebra. We introduce some results on monomial orders due to John Lawrence and the author. We show that a noncommutative monomial order is a well order while a one-sided noncommutative monomial order may not be. Then we discuss the generalization of polynomial reductions, S-polynomials and the characterizations of noncommutative Gröbner bases. Some results due to Mora are also discussed, such as the generalized Buchberger's algorithm and the solvability of ideal membership problem for homogeneous ideals. At last, we introduce Newman's diamond lemma and Bergman's diamond lemma and show their relations with Gröbner bases theory.
24
Fernandez, Roberto Daniel Torrealba. "Bases de Gröbner com coeficientes em anéis." Universidade de São Paulo, 2015. http://www.teses.usp.br/teses/disponiveis/55/55135/tde-28032016-165513/.
Full textAbstract:
Estudaremos a teoria de bases de Gröbner em anéis de polinômios comutativos com coeficientes em uma nelnoetheriano e em anéis de operadores diferencias. Apresentaremos, em ambos casos, uma generalização do algoritmo da divisão, do S-polinômio e do algoritmo de Buchberger para calcular bases de Gröbner.We study the theory of Gröbner bases for commutative polynomials rings over a noetherian ring and of rings of differential operators. In both cases we exhibit a generalization of the division algorithm, the S -polynomial and the Buchberger algorithm for computing Gröbner bases.
25
Helde, Andreas. "Noncommutative Gröbner bases in Polly Cracker cryptosystems." Thesis, Norwegian University of Science and Technology, Department of Mathematical Sciences, 2009. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-9928.
Full textAbstract:
We present the noncommutative version of the Polly Cracker cryptosystem, which is more promising than the commutative version. This is partly because many of the ideals in a free (noncommutative) algebra have an infinite Gröbner basis, which can be used as the public key in the cryptosystem. We start with a short brief of the commutative case which ends with the conclusion that the existence of "intelligent" linear algebra attacks ensures that such cryptosystems are left insecure. Further, we see that it is hard to prove that noncommutative ideals have an infinite reduced Gröbner basis for all admissible orders. Nevertheless, in chapter 4 we consider some ideals for which it seems infeasible to realize a finite Gröbner basis. These are considered further in a cryptographic setting, and there will be shown that one class of ideals seems more promising than the others with respect to encountering attacks on the cryptosystem. In fact, at the end of this thesis we are proposing a way of constructing a cryptosystem based on this class of ideals, such that any linear algebra attack will not be successful. However, many of the results are on experimental level, so there remains a serious amount of research in order to conclude that we have found a secure cryptosystem.
26
Schmidt, Natalia [Verfasser]. "Gröbner Bases in Coding Theory / Natalia Schmidt." München : Verlag Dr. Hut, 2015. http://d-nb.info/1074063236/34.
Full text
27
Djenderedjian, Ivan. "Bases de Gröbner minimales sur un anneau principal." Aix-Marseille 1, 2000. http://www.theses.fr/2000AIX11040.
Full textAbstract:
Cette these traite des bases de grobner a coefficients dans un anneau principal (z dans ce resume). Une nouvelle notion, celle de base de grobner minimale, y est definie. On montre qu'il y a unicite pour les termes dominants de ces bases minimales. Celles-ci permettent de clarifier la relation qui existe entre les bases de grobner faibles et fortes. Des algorithmes sont donnes pour calculer des bases de grobner faibles, minimales, et fortes ; ainsi que pour passer d'un type de ces bases a l'autre. Les bases de grobner minimales permettent de montrer que certains nombres premiers apparaissent toujours dans les denominateurs des coefficients d'une base de grobner unitaire d'un ideal de qx 1 x n. Elles permettent aussi de donner une reponse aux problemes de reduction d'une base de grobner d'un ideal de qx 1, , x n modulo un nombre premier. Les problemes d'extension (puis de restriction) d'un ideal i de zx 1, , x n a qx 1, , x n sont etudies ainsi que les liens entre les bases de grobner de i, iq et iqzx 1, , x n, ce qui produit des invariants independant de l'ordre monomial choisi. Un lien etroit entre les problemes d'extension et de reduction modulo un nombre premier est etabli.
28
Cabarcas, Daniel. "An Implementation of Faugère's F4 Algorithm for Computing Gröbner Bases." University of Cincinnati / OhioLINK, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1277120935.
Full text
29
Kvåle, Jarle. "Gröbner-baser og signaturskjemaet Unbalanced Oil and Vinegar." Thesis, Norwegian University of Science and Technology, Department of Mathematical Sciences, 2009. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-10537.
Full textAbstract:
Vi har i denne masteroppgaven sett nærmere på Gröbner-baser og signaturskjemaet Unbalanced Oil and Vinegar. Vi har sett nærmere på Gröbner-basenes definisjoner og sett hvordan Gröbner-baser kan genereres ved Buchbergers algoritme. Videre har vi sett hvordan Gröbner-baser hjelper for å gi resten i divisjonsalgoritmen i den multivariable polynomringen unikhet og indirekte dermed løse idealmedlemskapsproblemet. Videre undersøkte vi mulighetene for å bruke Gröbner-baser til å lage et offentlig nøkkel-kryptosystem. Foreløpig er det ingen som har greid å lage et slikt kryptosystem som har stått imot visse angrep. Den neste delen av oppgaven tok for seg signaturskjemaet Unbalanced Oil and Vinegar. Vi har presentert teorien bak UOV og sett nærmere på et enkelt eksempel. I tillegg har vi undersøkt tre angrep på UOV, der det ene var basert på Gröbner-baser. Det viser seg at UOV virker resistent mot disse angrepene gitt at vi tar visse forholdsregler med parametrene. For angrepet basert på Gröbner-baser må systemet være av en viss størrelse for at sikkerheten skal ivaretas. Avslutningsvis har vi sett på forbedrede algoritmer for å beregne Gröbner-baser. Den første algoritmen vi så på var $F_4$ -algoritmen som tok i bruk lineæralgebra, mens den andre, $F_5$-algoritmen, tok utgangspunkt i å kutte ut unødvendige beregninger. Det viser seg at både $F_4$- og $F_5$-algoritmen kraftig forbedrer beregningstiden for å finne en Gröbner-basis.
30
Marca, Castromonte Gustavo. "Bases de Gröbner con aplicaciones al álgebra conmutativa." Universidad Nacional de Ingeniería. Programa Cybertesis PERÚ, 2008. http://cybertesis.uni.edu.pe/uni/2008/marca_cg/html/index-frames.html.
Full text
31
Wilson, Michelle Marie Lucy. "A survey of primary decomposition using Gröbner bases." Thesis, Massachusetts Institute of Technology, 1994. http://hdl.handle.net/1721.1/37005.
Full text
32
Keller, Benjamin J. "Algorithms and Orders for Finding Noncummutative Gröbner Bases." Diss., Virginia Tech, 1997. http://hdl.handle.net/10919/30506.
Full textAbstract:
The problem of choosing efficient algorithms and good admissible orders for computing Gröbner bases in noncommutative algebras is considered. Gröbner bases are an important tool that make many problems in polynomial algebra computationally tractable. However, the computation of Gröbner bases is expensive, and in noncommutative algebras is not guaranteed to terminate. The algorithm, together with the order used to determine the leading term of each polynomial, are known to affect the cost of the computation, and are the focus of this thesis.
A Gröbner basis is a set of polynomials computed, using Buchberger's algorithm, from another set of polynomials. The noncommutative form of Buchberger's algorithm repeatedly constructs a new polynomial from a triple, which is a pair of polynomials whose leading terms overlap and form a nontrivial common multiple. The algorithm leaves a number of details underspecified, and can be altered to improve its behavior. A significant improvement is the development of a dynamic dictionary matching approach that efficiently solves the pattern matching problems of noncommutative Gröbner basis computations. Three algorithmic alternatives are considered: the strategy for selecting triples (selection), the strategy for removing triples from consideration (triple elimination), and the approach to keeping the set interreduced (set reduction).
Experiments show that the selection strategy is generally more significant than the other techniques, with the best strategy being the one that chooses the triple with the shortest common multiple. The best triple elimination strategy ignoring resource constraints is the Gebauer-Müller strategy. However, another strategy is defined that can perform as well as the Gebauer-Müller strategy in less space.
The experiments also show that the admissible order used to determine the leading term of a polynomial is more significant than the algorithm. Experiments indicate that the choice of order is dependent on the input set of polynomials, but also suggest that the length lexicographic order is a good choice for many problems. A more practical approach to chosing an order may be to develop heuristics that attempt to find an order that minimizes the number of overlaps considered during the computation.Ph. D.
33
Ars, Gwénolé. "Applications des bases de Gröbner à la cryptograhie." Rennes 1, 2005. http://www.theses.fr/2005REN1S039.
Full textAbstract:
Cette thèse est dédiée à la cryptanalyse algébrique par les bases de Gröbner. Nous avons justifié l'usage des bases de Gröbner par une comparaison théorique et expérimentale avec l'algorithme XL utilisé en cryptographie. Cette thèse a aussi pour objet l'étude de deux problèmes: les registres filtrés et l'AES. Pour prédire le résolution de ces systèmes, nous avons généralisé la notion d'Immunité Algébrique à tout corps fini et étudié les propriétés de cette notion (stabilité, bornes, relation avec d'autres critères cryptographiques). Pour les registres filtrés, une nouvelle représentation a explicité les relations linéaires de la mise en équations. Elle a permi d'obtenir une borne de complexité des attaques algébriques qui ont été vérifiées expérimentalement sur des registres de tailles réelles. Enfin, à travers des résolutions expérimentales d'une simplification appropriée de l'AES, nous avons déterminé des facteurs limitants (taille de la Sbox) ou non (nombre de cycles)
34
Saeed, Mohamed Ahmed. "Approche algébrique sur l'équivalence de codes." Thesis, Normandie, 2017. http://www.theses.fr/2017NORMR034/document.
Full textAbstract:
Le problème d’´équivalence de code joue un rôle important dans la théorie de code et la cryptographie basée sur le code. Cela est dû à son importance dans la classification des codes ainsi que dans la construction et la cryptanalyse des cryptosystèmes à base de codes. Il est également lié à un problème ouvert d’isomorphisme de graphes, un problème bien connu dans le domaine de la théorie de la complexité. Nous prouvons pour les codes ayant un hull trivial qu’il existe une réduction polynomiale de l’équivalence par permutation de codes à l’isomorphisme de graphes. Cela montre que cette sous-classe d’équivalence de permutation n’est pas plus dure que l’isomorphisme de graphes. Nous introduisons une nouvelle méthode pour résoudre le problème d’équivalence de code. Nous développons des approches algébriques pour résoudre le problème dans ses deux versions : en permutation et en diagonale. Nous construisons un système algébrique en établissant des relations entre les matrices génératrices et les matrices de parité des codes équivalents. Nous nous retrouvons avecun système plusieurs variables d’équations linéaires et quadratiques qui peut être résolu en utilisant des outils algébriques tels que les bases de Groebner et les techniques associées. Il est possible en théorie de résoudre l’équivalence de code avec des techniques utilisant des bases de Groebner. Cependant, le calcul en pratique devient complexe à mesure que la longueur du code augmente. Nous avons introduit plusieurs améliorations telles que la linéarisation par bloc et l’action de Frobenius. En utilisant ces techniques, nous identifions de nombreux cas où le problème d’équivalence de permutation peut être résolu efficacement. Notre méthode d’équivalence diagonale résout efficacement le problème dans les corps de petites tailles, à savoir F3 et F4. L’augmentation de la taille du corps entraîne une augmentation du nombre de variables dans notre système algébrique, ce qui le rend difficile à résoudre. Nous nous intéressons enfin au problème d’isomorphisme de graphes en considérant un système algébrique quadratique pour l’isomorphisme de graphes. Pour des instances tirées aléatoirement, le système possède des propriétés intéressantes en termes de rang de la partie linéaire et du nombre de variables. Nousrésolvons efficacement le problème d’isomorphisme de graphes pour des graphes aléatoires avec un grand nombre de sommets, et également pour certains graphes réguliers tels que ceux de Petersen, Cubical et Wagner.123Code equivalence problem plays an important role in coding theory and code based cryptography.That is due to its significance in classification of codes and also construction and cryptanalysis of code based cryptosystems. It is also related to the long standing problem of graph isomorphism, a well-known problem in the world of complexity theory. We introduce new method for solving code equivalence problem. We develop algebraic approaches to solve the problem in its permutation and diagonal versions. We build algebraic system by establishing relations between generator matrices and parity check matrices of the equivalent codes. We end up with system of multivariables of linear and quadratic equations which can be solved using algebraic tools such as Groebner basis and related techniques. By using Groebner basis techniques we can solve the code equivalence but the computation becomes complex as the length of the code increases. We introduced several improvements such as block linearization and Frobenius action. Using these techniques we identify many cases where permutation equivalence problem can be solved efficiently. Our method for diagonal equivalence solves the problem efficiently in small fields, namely F3 and F4. The increase in the field size results in an increase in the number of variables in our algebraic system which makes it difficult to solve. We introduce a new reduction from permutation code equivalence when the hull is trivial to graph isomorphism. This shows that this subclass of permutation equivalence is not harder than graph isomorphism.Using this reduction we obtain an algebraic system for graph isomorphism with interesting properties in terms of the rank of the linear part and the number of variables. We solve the graph isomorphism problem efficiently for random graphs with large number of vertices and also for some regular graphs such as Petersen, Cubical and Wagner Graphs
35
Capaverde, Juliane Golubinski. "Bases de Gröbner e aplicações em aproximações de Padé e codificação." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2009. http://hdl.handle.net/10183/17425.
Full textAbstract:
Nesta dissertação estudamos algumas aplicações da teoria das bases de Gröbner, visando principalmente a utilização dessas técnicas na teoria de códigos. Apresentamos um algoritmo para obter a base de Gröbner reduzida do ideal de um conjunto finito de pontos, e descrevemos um método para encontrar aproximações de Padé de polinômios multivariados. Terminamos apresentando o procedimento desenvolvido por J. Farr e S. Gao para a construção e decodificação de códigos lineares via bases de Gröbner.In this master thesis we study some applications of Grobner bases theory, aiming using these techniques in coding theory. We present an algorithm for computing the reduced Grobner basis of the vanishing ideal of a finite set of points, and describe a method for finding Padé approximations of multivariate polynomials. We finish presenting the procedure developed by J. Farr and S. Gao for construction and decoding of linear codes via Gröbner bases.
36
Nogueira, Filipa Nunes. "Bases de Gröbner e sistemas de equações às diferenças parciais." Master's thesis, Universidade de Aveiro, 2008. http://hdl.handle.net/10773/10472.
Full textAbstract:
Mestrado em Matemática e AplicaçõesNesta dissertação estuda-se o conceito de bases de Göbner para ideais de polinómios em várias indeterminadas. Este conceito é aplicado à obtenção de formas alternativas para sistemas de equações às diferenças parciais que se adequam ao cálculo recursivo das soluções.
In this thesis we study the concept of Gröbner bases for nD polynomial ideals. This concept is applied to the study of systems of partial difference equations, allowing alternative descriptions that are suitable for the recursive computation of solutions.
37
Svartz, Jules. "Résolution de systèmes polynomiaux structurés de dimension zéro." Electronic Thesis or Diss., Paris 6, 2014. http://www.theses.fr/2014PA066621.
Full textAbstract:
Les systèmes polynomiaux à plusieurs variables apparaissent naturellement dans de nombreux domaines scientifiques. Ces systèmes issus d'applications possèdent une structure algébrique spécifique. Une méthode classique pour résoudre des systèmes polynomiaux repose sur le calcul d'une base de Gröbner de l'idéal associé au système. Cette thèse présente de nouveaux outils pour la résolution de tels systèmes structurés, lorsque la structure est induite par l'action d'un groupe ou une structure monomiale particulière, qui englobent les systèmes multi-homogènes ou quasi-homogènes. D'une part, cette thèse propose de nouveaux algorithmes qui exploitent ces structures algébriques pour améliorer l'efficacité de la résolution de systèmes (systèmes invariant sous l'action d'un groupe ou à support dans un ensemble de monômes particuliers). Ces techniques permettent notamment de résoudre un problème issu de la physique pour des instances hors de portée jusqu'à présent. D'autre part, ces outils permettent d'améliorer les bornes de complexité de résolution de plusieurs familles de systèmes polynomiaux structurés (systèmes globalement invariant sous l'action d'un groupe abélien, individuellement invariant sous l'action d'un groupe quelconque, ou ayant leur support dans un même polytope). Ceci permet en particulier d'étendre des résultats connus sur les systèmes bilinéaires aux systèmes mutli-homogènes générauxMultivariate polynomial systems arise naturally in many scientific fields. These systems coming from applications often carry a specific algebraic structure.A classical method for solving polynomial systems isbased on the computation of a Gr\"obner basis of the ideal associatedto the system.This thesis presents new tools for solving suchstructured systems, where the structure is induced by the action of a particular group or a monomial structure, which include multihomogeneous or quasihomogeneous systems.On the one hand, this thesis proposes new algorithmsusing these algebraic structures to improve the efficiency of solving suchsystems (invariant under the action of a group or having a support in a particular set of monomials). These techniques allow to solve a problem arising in physics for instances out of reach until now.On the other hand, these tools improve the complexity bounds for solving several families of structured polynomial systems (systems globally invariant under the action of an abelian group or with their support in the same polytope). This allows in particular to extend known results on bilinear systems to general mutlihomogeneous systems
38
Basiri, Abdolali. "Bases de Gröbner et LLL : arithmétique rapide des courbes C ab." Paris 6, 2003. http://www.theses.fr/2003PA066358.
Full text
39
Svartz, Jules. "Résolution de systèmes polynomiaux structurés de dimension zéro." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066621/document.
Full textAbstract:
Les systèmes polynomiaux à plusieurs variables apparaissent naturellement dans de nombreux domaines scientifiques. Ces systèmes issus d'applications possèdent une structure algébrique spécifique. Une méthode classique pour résoudre des systèmes polynomiaux repose sur le calcul d'une base de Gröbner de l'idéal associé au système. Cette thèse présente de nouveaux outils pour la résolution de tels systèmes structurés, lorsque la structure est induite par l'action d'un groupe ou une structure monomiale particulière, qui englobent les systèmes multi-homogènes ou quasi-homogènes. D'une part, cette thèse propose de nouveaux algorithmes qui exploitent ces structures algébriques pour améliorer l'efficacité de la résolution de systèmes (systèmes invariant sous l'action d'un groupe ou à support dans un ensemble de monômes particuliers). Ces techniques permettent notamment de résoudre un problème issu de la physique pour des instances hors de portée jusqu'à présent. D'autre part, ces outils permettent d'améliorer les bornes de complexité de résolution de plusieurs familles de systèmes polynomiaux structurés (systèmes globalement invariant sous l'action d'un groupe abélien, individuellement invariant sous l'action d'un groupe quelconque, ou ayant leur support dans un même polytope). Ceci permet en particulier d'étendre des résultats connus sur les systèmes bilinéaires aux systèmes mutli-homogènes générauxMultivariate polynomial systems arise naturally in many scientific fields. These systems coming from applications often carry a specific algebraic structure.A classical method for solving polynomial systems isbased on the computation of a Gr\"obner basis of the ideal associatedto the system.This thesis presents new tools for solving suchstructured systems, where the structure is induced by the action of a particular group or a monomial structure, which include multihomogeneous or quasihomogeneous systems.On the one hand, this thesis proposes new algorithmsusing these algebraic structures to improve the efficiency of solving suchsystems (invariant under the action of a group or having a support in a particular set of monomials). These techniques allow to solve a problem arising in physics for instances out of reach until now.On the other hand, these tools improve the complexity bounds for solving several families of structured polynomial systems (systems globally invariant under the action of an abelian group or with their support in the same polytope). This allows in particular to extend known results on bilinear systems to general mutlihomogeneous systems
40
Wailly, Olivier. "Placement optimal de capteurs sur un système à modèle polynomial." Corte, 2004. http://www.theses.fr/2005CORT3091.
Full textAbstract:
La présente thèse met en évidence une méthode novatrice dans le placement de capteurs sur un système automatisé. Cette méthode n'est applicable que sur les systèmes présentant un modèle polynomial. Cette méthode est innovante dans l'utilisation du calcul formel, et plus spécifiquement des algorithmes des bases de Groëbner. Après avoir montré comment il est possible, utile et interressant d'utiliser le calcul formel, il est développé une recherche de placement prenant en compte des critères optimums. Ainsi, des algorithmes avec critères de coût et critères de fiabilité sont élaborésThe present thesus present a novel method in sensor design on automated system. This method is only applicable on polynomial systems. This method is using symbolic calculus software. Especially, the Groënberg bases' algorithms are used. After showing the interest of this method, algoritms and programs with optimal criteria are presented. So, the criteria like cost and reliability are developed
41
Busse, Philip. "MULTIVARIATE LIST DECODING OF EVALUATION CODES WITH A GRÖBNER BASIS PERSPECTIVE." UKnowledge, 2008. http://uknowledge.uky.edu/gradschool_diss/627.
Full text
42
Xiu, Xingqiang [Verfasser], and Martin [Akademischer Betreuer] Kreuzer. "Non-commutative Gröbner Bases and Applications / Xingqiang Xiu. Betreuer: Martin Kreuzer." Passau : Universitätsbibliothek der Universität Passau, 2012. http://d-nb.info/1024803708/34.
Full text
43
Apel, Joachim, Jürgen Stückrad, Piotr Tworzewski, and Tadeusz Winiarski. "Reduction of everywhere convergent power series with respect to Gröbner bases." Universität Leipzig, 1994. https://ul.qucosa.de/id/qucosa%3A34418.
Full textAbstract:
We introduce a notion of Gröbner reduction of everywhere convergent power series over the real or
complex numbers with respect to ideals generated by polynomials and an admissible term ordering.
The presented theory is situated somewhere between the known theories for polynomials and formal
power series.
Our main theorem states the existence of a formula for the division of everywhere convergent power
series over the real or complex numbers by a finite set of polynomials. If the set of polynomials is
a Gröbner basis then the remainder of that division depends only on the equivalence class of the
power series modulo the ideal generated by the polynomials. When the power series which shall be
divided is a polynomial the division formula leads to a usual Gröbner representation well known
from polynomial rings.
Finally, the results are applied to prove the closedness of ideals generated by polynomials in the
ring of everywhere convergent power series and to give a very simple proof of the affine version of
Serre's graph theorem.
44
Chenavier, Cyrille. "Le treillis des opérateurs de réduction : applications aux bases de Gröbner non commutatives et en algèbre homologique." Thesis, Sorbonne Paris Cité, 2016. http://www.theses.fr/2016USPCC334.
Full textAbstract:
Dans cette thèse, on étudie les algèbres associatives unitaires par des méthodes de réécriture. La théorie des bases de \G\ non commutatives permet de résoudre des problèmes de décidabilité ou de calculer des invariants homologiques par de telles méthodes. Motivé par des questions d'algèbre homologique, Berger caractérise les bases de \G\ quadratiques en termes de treillis. Cette caractérisation a pour base les opérateurs de réduction. Ceux-ci sont des projecteurs particuliers d'un espace vectoriel admettant une base totalement ordonnée. Berger montre que, dans le cas où cet espace vectoriel est de dimension finie, l'ensemble des opérateurs de réduction admet une structure de treillis. Il en déduit une formulation de la confluence en termes de treillis lui permettant de caractériser les bases de \G\ quadratiques. Dans ce travail, on étend l'approche par les opérateurs de réduction en l'appliquant au cas des algèbres non nécessairement quadratiques. Pour cela, on montre qu'en dimension quelconque l'ensemble des opérateurs de réduction admet également une structure de treillis. En dimension finie, celle-ci coïncide avec celle exhibée par Berger. On en déduit une formulation de la confluence en termes de treillis généralisant celle de Berger. En outre, on donne une interprétation de la complétion en termes de treillis.La formulation algébrique de la confluence permet en particulier des caractériser les bases de \G\ non commutatives en termes de treillis. De plus, la formulation algébrique de la complétion, nous permet de montrer que celle-ci peut être obtenue via une construction dans le treillis des opérateurs de réduction. On en déduit une méthode pour construire des bases de \G\ non commutatives.On construit également une homotopie contractante du complexe de Koszul en termes d'opérateurs de réduction. La formulation de la confluence en termes de treillis nous permet de caractériser celle-ci par des équations. Ces équations induisent des représentations d'une famille d'algèbres que sont les algèbres de confluence. L'homotopie contractante est construite à partir de ces représentationsIn this thesis, we study associative unitary algebras with rewriting methods. \G\ bases theory enables us to solve decision problems and to compute homological invariants with such methods. In order to study homological problems, Berger characterises quadratic \G\ bases in a lattice way. This characterisationis obtained using reduction operators. The latter ones are specific projectors of a vector space equipped with a wellfounded basis. When this vector space is finite-dimensional, Berger proves that the associated set of reduction operators admits a lattice structure. Using it, he deduces the lattice characterisation of quadratic \G\ bases. In this thesis, we extend the approach in terms of reduction operators applying it to not necessarily quadratic algebras.For that, we show that the set of reduction operators relative to a not necessarily finite-dimensional vector space admitsa lattice structure. In the finite-dimensional case, we obtain the same lattice structure than Berger's one. We provide a lattice formulation of confluence generalizing Berger's one. Moreover, we provide a lattice characterisation of completion.We use the lattice formulation of confluence to characterise non commutative \G\ bases. Moreover, we deduce from the lattice formulation of confluence a procedure to construct non commutative \G\ bases.We also construct a contracting homotopt for the Koszul complex using reduction operators. The lattice formulation of confluence enables us to characterise it with algebraic equations. These equations induce representations of a family of algebras called confluence algebras. Our contracting homotopy is built using these representations
45
Renaud, Ruixian. "Génération des conditions d'existence d'une classe de systèmes de solides surcontraints avec les bases de Gröbner." Phd thesis, Ecole Centrale Paris, 2014. http://tel.archives-ouvertes.fr/tel-01020268.
Full textAbstract:
En cinématique il n'existe aucune méthode permettant de générer les conditions d'assemblage sous forme symbolique pour les systèmes de solides, éventuellement surcontraints. En revanche il existe un grand nombre de formules permettant- en principe - de calculer la mobilité. Les noms de Kutzbach, Grübler et Tchebytcheff sont associés à différentes formules bien connues mais aucune formule infaillible n'a jamais été trouvée. C'est ce qui motive notre proposition de méthodes numériques et symboliques constructives. Celles-ci permettent de générer automatiquement les conditions d'assemblage et de mobilité à partir de la connaissance des équations de fermeture des boucles de solides. Les méthodes numérique et symbolique présentées dans cette thèse se basent sur un socle commun. Elles utilisent les paramètres de Denavit-Hartenberg et les classent en deux catégories: la première catégorie, notée u pour usinage, représente les dimensions géométriques des solides, la seconde, notée m pour mobilité, représente les paramètres de position relative de deux solides en contact. Ensuite, les équations de fermeture sont obtenues par une méthode ''coordinate free'' à partir d'une matrice de Gram. C'est à cette étape que les deux méthodes diffèrent. Dans le cas de l'analyse numérique locale, le système d'équations est linéarisé. La décomposition en valeur singulière est utilisée pour l'élimination des paramètres. Nous obtenons ensuite les conditions d'assemblage dans un voisinage de la configuration initiale. Les conditions de mobilité sont calculées à partir des conditions d'assemblage issues d'un nombre fini de configurations. Dans le cas de l'analyse symbolique, nous calculons formellement la base de Gröbner associée aux équations de fermeture et cela grâce à l'algorithme FGb de Faugère. Il existe peu de références sur l'utilisation des Bases de Gröbner en cinématique, et aucune ne présente une analyse exhaustive du problème. Avec l'ordre lexicographique, nous ne gardons que des paramètres u et éliminons tous les autres. Lorsque ces relations en u sont vérifiées, elles représentent les conditions d'assemblage, dites relations de surcontraintes. Cet ensemble peut être vide lorsque le système est isocontraint. Pour générer les conditions de mobilité, nous gardons tous les u et un paramètre de mobilité. En annulant les coefficients en facteur de ce paramètre de mobilité, un nouveau système qui ne dépend que de u est construit. Les conditions de mobilité sont obtenues en calculant la base de Gröbner du nouveau système. Pour atteindre les résultats désirés, nous avons également proposé deux outils: saturation et contrainte. Ils permettent de parcourir un sous-ensemble de solutions représentées par une base de Gröbner. La confrontation des résultats obtenus dans la thèse avec ceux de la littérature, pour quelques de mécanismes connus, permet d'affirmer la validité et la complétude de la méthode.
46
Ali, Anissa. "Représentation et analyse algébriques de système de solides sur-contraints en boucle fermée." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLC062.
Full textAbstract:
Un système de solides peut être classé suivant trois états de mobilité: l’état non assemblé, l’état assemblé rigide et l’état assemblé mobile. L’étude se focalise sur les systèmes de solides sur-contraints en boucle fermée. Lors de l’étape de conception ou reconception, les dimensions d’un système de solides sur-contraints sont amenées à être modifiées, ce qui peut avoir pour conséquence la perte de son état de mobilité.L’approche présentée dans cette thèse a pour but de proposer une assistance au concepteur lors du redimensionnement, lui permettant de modifier ou conserver l’état de mobilité d’un système de solides. Le redimensionnement de systèmes de solides sur-contraints nécessite la connaissance de relations dépendant de leurs dimensions: les équations d’assemblage et les conditions de mobilité. Ces relations sont obtenues à l’aide d’un outil de résolution algébrique: les bases de Gröbner. La résolution algébrique est parfois coûteuse, voire impossible en un temps raisonnable, c’est ce qui justifie les méthodes décrites dans cette thèse.La solution proposée est composée de deux étapes principales. Tout d’abord, les représentations algébriques d’un système de solides fermé et mobile sont décrites. Les équations de fermeture d’un système de solides composé de plusieurs boucles sont obtenues en utilisant un paramétrage en coordonnées relatives. Les équations de mobilité sont elles générées à partir des équations de fermeture, à l’aide de méthodes directes ou incrémentales. Ensuite, afin de faciliter la génération des équations d’assemblage et de mobilité, une analyse algébrique reposant sur des outils d’analyse numérique est définie. L’état de mobilité du système de solides à redimensionner est déterminé à partir d’un ensemble de valeurs des paramètres le décrivant. Si le concepteur souhaite modifier l’état de mobilité du système de solides, de nouvelles valeurs sont alors générées. Lorsque l’état de mobilité souhaité est obtenu, il est possible de varier les dimensions tout en conservant cet état. Pour cela, certaines dimensions sont spécialisées afin de faciliter la génération des équations d’assemblage et des conditions de mobilité. Si les paramètres choisis sont liés ou trop nombreux, l’analyse mène inéluctablement à une absence de solutions. Des stratégies de partitionnement pour pallier ces problèmes sont aussi proposées. Enfin, les outils développés dans le logiciel Maple® afin d’illustrer les différents concepts proposés sont présentés, et un outil interactif permettant au concepteur de naviguer sur les équations de fermeture, équations d’assemblage et les conditions de mobilité obtenues après spécialisation, est proposéAn assembly can be partitioned into three mobility states: the impossible state, the rigid state and the mobile state. The study focuses in over-constrained closed-loop assemblies. During the process of design or re-design, the dimensions of the assembly can vary and this can lead to the loss of its mobility state.The method presented in this thesis aims at helping the designer to resize an assembly. There exist relationships between the dimension of the assembly that ensure the closure and the mobility of over-constrained. These relationships called assembly equations and mobility conditions are hence necessary to resize an over-constrained solid assembly. Assembly equations and mobility conditions are computed by a computer algebra tool: Gröbner bases. However, the algebraic solving using Gröbner bases can be costly and may fail because of unreasonable computing time, this is the main reason of the strategies described in this thesis.The approach proposed in this thesis is composed of two main steps. First of all, an algebraic representation of a closed assembly and a mobile assembly is descibed. The closed-loop equations are written by using a coordinate free method and the mobility equations are generated from the closed-loop equations using direct and incremental methods. To simplify the computation of assembly equations and mobility conditions an algebraic analysis that rely on numerical analysis tools is proposed. Starting from a set of values of the parameters that describe the assembly to resize, the mobility state of the assembly is determined. Then, if the designer want to change the mobility state, a new set of values that have the mobility state chosen by the designer is generated. Once the initial set of values has the right mobility state, some dimensions are specialized to ease the computation of assembly equations and mobility conditions. However, if the parameters chosen are linked or its number is to high, there is a high chance that the study lead to no solution. Strategies to avoid these problems are also proposed. Finally, the tools developped in Maple® software that illustrate the methods proposed are described and an interactive tool that permits the designer to visualize the solutions of the closed-loop equations, assembly equations and mobility conditions computed after specialisation is proposed
47
Tiwari, Sharwan Kumar [Verfasser]. "Algorithms in Noncommutative Algebras: Gröbner Bases and Hilbert Series / Sharwan Kumar Tiwari." München : Verlag Dr. Hut, 2017. http://d-nb.info/1149579307/34.
Full text
48
Chan, Andrew John. "Gröbner bases over fields with valuation and tropical curves by coordinate projections." Thesis, University of Warwick, 2013. http://wrap.warwick.ac.uk/59163/.
Full textAbstract:
In the emerging field of tropical geometry, algebraic varieties are replaced by polyhedral objects called tropical varieties. The algebraic and tropical variety share many invariants, but due to its polyhedral structure the tropical variety is often easier to work with. In this thesis, we look at two problems related to constructing tropical varieties. In the first, we extend the theory of Grobner bases to the case where we are looking over a field with a valuation. The motivation is that we can use these Grobner bases in order to compute tropical varieties over fields with valuations. We discuss some complexity and implementation issues and present a family of ideals whose Grobner basis with respect to the p-adic valuation is small, but all of whose standard Grobner bases are large. In the second, we investigate finding tropical curves over fields with the trivial valuation from their two-dimensional coordinate projections. A tropical curve has the support of a one-dimensional fan, and we use its coordinate projections to reconstruct the rays of this fan. We discuss some implementation issues and we see examples of tropical curves which can be computed using our projection techniques which cannot be computed with existing techniques.
49
Billet, Olivier François André. "Cryptologie multivariable." Versailles-St Quentin en Yvelines, 2005. http://www.theses.fr/2005VERS0023.
Full textAbstract:
La cryptographie multivariable est un domaine de recherche prometteur en cryptologie. Nous exposons dans une première partie de ce mémoire les principales constructions proposées à ce jour : le schéma de T. Matsumoto et H. Imai, les multiples constructions de J. Patarin, ainsi que les schémas les plus récents. Les principales techniques de cryptanalyse de ces cryptosystèmes sont également décrites. Une seconde partie propose le premier cryptosystème multivarié utilisable dans un contexte de groupe : une nouvelle construction permettant le traçage des traîtres. Une troisième partie est consacrée à la cryptanalyse d'une technique d'obscurcissement d'algorithmes cryptographiques. Nous exposons enfin les attaques algébriques contre les systèmes de chiffrement. Après avoir introduit le concept de base de Gröbner,nous décrivons notre implantation de l'algorithme F4 dédiée aux calculs sur les systèmes booléens. Nous présentons pour conclure une attaque algébrique contre le système de chiffrement par flot Snow 2. 0Multivariate cryptography is a very promising research area of cryptology. In this thesis, we report the main cryptographic constructions to date: the scheme of T. Matsumoto and H. Imai, the various proposals of J. Patarin, as well as the most recent constructions. We also provide a description of the main cryptanalysis techniques in this setting. A second part describes the very first mutivariate cryptosystem in a group setting, namely a traitor tracing scheme. A third part is dedicated to the cryptanalysis of a white boximplementation of the AES bloc cipher. Eventually, we explain algebraic attacks against ciphers. After a brief introduction on Gröbner bases, we describe our implementation dedicated to omputations on boolean systems of the algorithm F4. We conclude by a description of an algebraic attack on the Snow 2. 0 cipher
50
Spaenlehauer, Pierre-Jean. "Résolution de systèmes multi-homogènes et déterminantiels algorithmes - complexité - applications." Paris 6, 2012. http://www.theses.fr/2012PA066467.
Full textAbstract:
De nombreux systèmes polynomiaux multivariés apparaissant en Sciences de l'Ingénieur possèdent une structure algébrique spécifique. En particulier, les structures multi-homogènes, déterminantielles et les systèmes booléens apparaissent dans une variété d'applications. Une méthode classique pour résoudre des systèmes polynomiaux passe par le calcul d'une base de Gröbner de l'idéal associé au système. Cette thèse présente de nouveaux outils pour la résolution de tels systèmes structurés. D'une part, ces outils permettent d'obtenir sousdes hypothèses de généricité des bornes de complexité du calcul debase de Gröbner de plusieurs familles de systèmes polynomiauxstructurés (systèmes bilinéaires, systèmes déterminantiels, systèmesdéfinissant des points critiques, systèmes booléens). Ceci permetd'identifier des familles de systèmes pour lequels la complexité arithmétique de résolution est polynomiale en le nombre de solutions. D'autre part, cette thèse propose de nouveaux algorithmequi exploitent ces structures algébriques pour améliorer l'efficacité du calcul de base de Gröbner et de la résolution (systèmes multi-homogènes, systèmes booléens). Ces résultats sontillustrés par des applications concrètes en cryptologie (cryptanalyse des systèmes MinRank et ASC), en optimisation et en géométrie réelle effective (calcul de points critiques)Multivariate polynomial systems arising in Engineering Science often carryalgebraic structures related to the problems they stem from. Inparticular, multi-homogeneous, determinantal structures and booleansystems can be met in a wide range of applications. A classical method to solve polynomial systems is to compute a Gröbner basis ofthe ideal associated to the system. This thesis provides new tools forsolving such structured systems in the context of Gröbner basis algorithms. On the one hand, these tools bring forth new bounds on the complexity of thecomputation of Gröbner bases of several families of structured systems(bilinear systems, determinantal systems, critical point systems,boolean systems). In particular, it allows the identification of families ofsystems for which the complexity of the computation is polynomial inthe number of solutions. On the other hand, this thesis provides new algorithms which takeprofit of these algebraic structures for improving the efficiency ofthe Gröbner basis computation and of the whole solving process(multi-homogeneous systems, boolean systems). These results areillustrated by applications in cryptology (cryptanalysis of MinRank),in optimization and in effective real geometry (critical pointsystems)