(Downloads - 0)
For more info about our services contact : help@bestpfe.com
Table of contents
Introduction
I Preliminaries
1 Gr¨obner bases
1.1 Polynomial Rings and Ideals
1.1.1 Definitions
1.1.2 Modules, algebras and free resolutions
1.1.3 Primary decomposition and associated primes
1.2 Monomial orderings and Gr¨obner bases
1.2.1 Definitions
1.2.2 Gradings on polynomial rings
1.2.3 Regular and Semi-regular Sequence
1.2.4 Boolean semi-regular systems.
1.3 Polynomial system solving
1.3.1 Gr¨obner basis Algorithms
1.3.2 Matrix F5 Algorithm
1.3.3 FGLM Algorithm
1.4 Degree bounds
1.4.1 Definitions
1.4.2 Degree of regularity
1.4.3 Relations between notions of regularity
1.5 Complexity
1.5.1 Complexity model
1.5.2 Complexity of Gr¨obner basis algorithms
1.5.3 Complexity of solving affine systems
1.5.4 Complexity and degree of the ideal
2 Algebraic Systems in Applications
2.1 MinRank
2.1.1 Description of the MinRank problem
2.1.2 Algebraic techniques for solving the MinRank problem
2.2 Cryptology and Information Theory
2.2.1 Courtois Authentication Scheme
2.2.2 Rank metric codes
2.2.3 Hidden Field Equations (HFE)
2.2.4 McEliece PKC.
2.2.5 QUAD
2.2.6 The Algebraic Surface Cryptosystem
2.3 Real Solving and Optimization
2.3.1 Problem statements
2.3.2 Algebraic Tools for Real Solving
3 Determinantal and multi-homogeneous systems
3.1 Determinantal systems
3.2 Structure of multi-homogeneous ideals
3.3 Affine bilinear systems
II Contributions
4 Determinantal Systems
4.1 Introduction
4.2 Notations and preliminaries
4.3 Transferring determinantal properties
4.4 The case n ≥ (p − r)(q − r)
4.5 The over-determined case
4.6 Complexity analysis
4.6.1 Positive dimension
4.6.2 The 0-dimensional affine case
4.7 Case studies
4.7.1 D grows, p, q, r are fixed
4.7.2 p grows, q, r,D are fixed
4.7.3 The case r = q − 1
4.7.4 Experimental results
5 Critical Point Systems
5.1 Introduction
5.2 Preliminaries
5.3 The homogeneous case
5.3.1 Auxiliary results
5.3.2 Proof of Proposition 5.7
5.4 The affine case
5.5 Complexity
5.6 Experimental Results
5.7 Mixed systems
5.7.1 Eagon-Northcott complex
5.7.2 Hilbert series, degree of regularity
5.7.3 Complexity
6 Multi-Homogeneous Systems
6.1 Introduction
6.2 Computing Gr¨obner bases of bilinear systems
6.2.1 Overview
6.2.2 Jacobian matrices of bilinear systems and syzygies
6.2.3 Maximal minors of linear matrices
6.2.4 An extension of the F5 criterion for bilinear systems
6.3 F5 without reduction to zero for generic bilinear systems
6.3.1 Main results
6.3.2 Kernel of matrices whose entries are linear forms
6.3.3 Structure of generic bilinear systems
6.4 Hilbert bi-series of bilinear systems
6.5 Towards complexity results
6.5.1 A multihomogeneous F5 Algorithm
6.5.2 Complexity estimates
6.5.3 Number of reductions to zero
6.5.4 Structure of generic affine bilinear systems
6.5.5 Affine bilinear systems – maximal degree reached
6.6 Bi-homogeneous systems of bi-degree (D, 1)
7 Boolean Systems
7.1 Introduction
7.2 Algorithm
7.2.1 Macaulay matrix
7.2.2 Witness degree
7.2.3 Algorithm
7.2.4 Testing Consistency of Sparse Linear Systems
7.3 Complexity Analysis
7.3.1 Sizes of Macaulay Matrices
7.3.2 Bound on the Witness Degree of Inconsistent Systems
7.3.3 Complexity
7.4 Numerical Experiments on Random Systems
7.4.1 γ-strong semi-regularity
7.4.2 Numerical estimates of the complexity
7.5 Extensions and Applications
7.5.1 Adding Redundancy to Avoid Rank Defects
7.5.2 Improving the quality of the filtering for small values of n
7.5.3 Cases with Low Degree of Regularity
8 Application to Cryptology
8.1 Cryptanalysis of the Algebraic Surface Cryptosystem
8.1.1 Introduction
8.1.2 Description of the cryptosystem
8.1.3 Description of the attack
8.1.4 Level 1 Attack: decomposition of ideals.
8.1.5 Level 2 Attack: computing in the field of fractions GFp(t)
8.1.6 Level 3 Attack: computing in finite fields GFpm
8.1.7 Complexity analysis
8.1.8 Experimental results
8.1.9 Conclusion
8.1.10 Toy example
8.1.11 MAGMA code for the Level 1 Attack
8.2 Cryptanalysis of MinRank
8.2.1 Computing the minors
8.2.2 The well-defined case
8.2.3 Solving the challenge C of the Courtois authentication scheme
8.3 Analysis of QUAD
