没有合适的资源?快使用搜索试试~ 我知道了~
首页2009年Gregory V. Bard的代数密码学论文集
2009年Gregory V. Bard的代数密码学论文集
需积分: 11 0 下载量 9 浏览量
更新于2024-06-28
收藏 2.17MB PDF 举报
"《代数密码分析:Gregory V. Bard著,2009》是一本深入探讨代数方法在密码学中的应用和技术分析的学术著作。该书由Gregory V. Bard撰写,于2009年发布,专为密码学领域的专业人士和研究者设计,详细阐述了代数方法如何在密码系统的设计、分析和破解中发挥关键作用。代数密码学是密码学的一个分支,它利用抽象的数学结构,如群论、环论和域论,来构造和分析加密算法,确保其安全性。
书中可能涵盖了以下知识点:
1. 基本概念:代数工具如线性代数、多项式密码体制(如RSA和椭圆曲线加密)、有限域和有限域上的离散对数问题,这些都是代数密码学的基础。
2. 攻击与防御:书中会介绍针对代数密码系统的攻击方法,如差分密码分析、线性密码分析和指数攻击,同时也会讨论如何通过改进设计来增强抵抗这些攻击的能力。
3. 典型算法:可能会深入剖析AES、RSA、ElGamal等著名密码算法的代数特性,以及它们在代数攻击下的弱点和优化策略。
4. 最新进展:2009年的研究可能反映了当时代数密码学的前沿动态,包括新型密码体制的设计、零知识证明和同态加密等领域的创新。
此外,书中还可能包含关于密码学会议(如Eurocrypt、Crypto和Asiacrypt)的论文集,这些会议是代数密码学领域的重要交流平台,书中引用的研究成果通常会在这些会议上发表,体现了该领域的最新研究趋势。
数缘社区作为一个专业的数学和密码学论坛,提供了丰富的资源库,包括1981年至2003年所有欧密会和美密会论文,以及部分后续会议的论文,这为读者学习和研究代数密码学提供了宝贵的参考资料。论坛成员不仅来自山东大学数学院,而且在密码学和网络安全领域具备深厚的学术背景,这使得该社区成为了一个学习和探讨先进加密技术的绝佳之地。
对于希望进一步了解代数密码学的人来说,阅读《代数密码分析》这本书以及利用数缘社区的资源,将有助于深入理解这一复杂但至关重要的领域,并在密码学的安全实践和理论研究中取得突破。"
xviii Contents
3.2 The Consequences of Fixed Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 How to Find Fixed Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 How far must we search? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.4.1 With Analytic Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.4.2 Without Analytic Combinatorics . . . . . . . . . . . . . . . . . . . . . . . 23
3.5 Comparison to Brute Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.7 Other Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.7.1 A Note about Keeloq’s Utilization . . . . . . . . . . . . . . . . . . . . . . 25
3.7.2 RPA vs KPA vs CPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.8 Wagner’s Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.8.1 Later Work on Keeloq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 Iterated Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.1 Applications to Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2.1 Combinatorial Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2.2 Ordinary and Exponential Generating Functions . . . . . . . . . . 30
4.2.3 Operations on OGFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.5 Operations on EGFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2.6 Notation and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Strong and Weak Cycle Structure Theorems . . . . . . . . . . . . . . . . . . . . 40
4.3.1 Expected Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.4 Corollaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4.1 On Cycles in Iterated Permutations . . . . . . . . . . . . . . . . . . . . . 45
4.4.2 Limited Cycle Counts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4.3 Monomial Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5 Of Pure Mathematical Interest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5.1 The Sigma Divisor Function . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.5.2 The Zeta Function and Ap
´
ery’s Constant . . . . . . . . . . . . . . . . . 48
4.5.3 Greatest Common Divisors and Cycle Length . . . . . . . . . . . . 49
4.6 Highly Iterated Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.6.1 Distinguishing Iterated Ciphers . . . . . . . . . . . . . . . . . . . . . . . . 50
4.6.2 A Key Recovery Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5 Stream Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.1 The Stream Ciphers Bivium and Trivium . . . . . . . . . . . . . . . . . . . . . . . 55
5.1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.1.2 Bivium as Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.1.3 An Excellent Trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.1.4 Bivium-A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.1.5 A Notational Issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.1.6 For Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2 The Stream Cipher QUAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Contents xix
5.2.1 How QUAD Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2.2 Proof of Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2.3 The Yang-Chen-Bernstein-Chen Attack against QUAD . . . . 72
5.2.4 Extending to GF(16) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2.5 For Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.3 Conclusions for QUAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Part II Linear Systems Mod 2
6 Some Basic Facts about Linear Algebra over GF(2) . . . . . . . . . . . . . . . . 81
6.1 Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2 Boolean Matrices vs GF(2) Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2.1 Implementing with the Integers . . . . . . . . . . . . . . . . . . . . . . . . 82
6.3 Why is GF(2) Different? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.3.1 There are Self-Orthogonal Vectors . . . . . . . . . . . . . . . . . . . . . . 82
6.3.2 Something that Fails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3.3 The Probability a Random Square Matrix Singular or
Invertible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.4 Null Space from the RREF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.5 The Number of Solutions to a Linear System . . . . . . . . . . . . . . . . . . . 86
7 The Complexity of GF(2)-Matrix Operations . . . . . . . . . . . . . . . . . . . . . . 89
7.1 The Cost Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.1.1 A Word on Architecture and Cross-Over . . . . . . . . . . . . . . . . . 90
7.1.2 Is the Model Trivial? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.1.3 Counting Field Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.1.4 Success and Failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.2 Notational Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.3 To Invert or to Solve? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.4 Data Structure Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.4.1 Dense Form: An Array with Swaps . . . . . . . . . . . . . . . . . . . . . 94
7.4.2 Permutation Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.5 Analysis of Classical Techniques with our Model . . . . . . . . . . . . . . . . 96
7.5.1 Na
¨
ıve Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.5.2 Matrix Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.5.3 Dense Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.5.4 Back-Solving a Triangulated Linear System . . . . . . . . . . . . . . 98
7.6 Strassen’s Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.6.1 Strassen’s Algorithm for Matrix Multiplication . . . . . . . . . . . 100
7.6.2 Misunderstanding Strassen’s Matrix Inversion Formula . . . . 101
7.7 The Unsuitability of Strassen’s Algorithm for Inversion . . . . . . . . . . . 101
7.7.1 Strassen’s Approach to Matrix Inversion . . . . . . . . . . . . . . . . . 102
7.7.2 Bunch and Hopcroft’s Solution . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.7.3 Ibara, Moran, and Hui’s Solution . . . . . . . . . . . . . . . . . . . . . . . 103
xx Contents
8 On the Exponent of Certain Matrix Operations . . . . . . . . . . . . . . . . . . . . 107
8.1 Very Low Exponents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
8.2 The Equicomplexity Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
8.2.1 Starting Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.2.2 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.3 Determinants and Matrix Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
8.3.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
8.3.2 The Baur-Strassen-Morgenstern Theorem . . . . . . . . . . . . . . . . 120
8.3.3 Consequences for the Determinant and Inverse . . . . . . . . . . . 132
9 The Method of Four Russians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
9.0.4 The Fair Coin Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
9.1 Origins and Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
9.1.1 Strassen’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.2 Rapid Subspace Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.3 The Four Russians Matrix Multiplication Algorithm . . . . . . . . . . . . . 137
9.3.1 Role of the Gray Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9.3.2 Transposing the Matrix Product . . . . . . . . . . . . . . . . . . . . . . . . 138
9.3.3 Improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9.3.4 A Quick Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
9.3.5 M4RM Experiments Performed by S
AGE Staff . . . . . . . . . . . 139
9.3.6 Multiple Gray-Code Tables and Cache Management . . . . . . . 141
9.4 The Four Russians Matrix Inversion Algorithm . . . . . . . . . . . . . . . . . . 141
9.4.1 Stage 1: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9.4.2 Stage 2: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
9.4.3 Stage 3: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
9.4.4 A Curious Note on Stage 1 of M4RI . . . . . . . . . . . . . . . . . . . . 143
9.4.5 Triangulation or Inversion? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
9.5 Exact Analysis of Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
9.5.1 An Alternative Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
9.5.2 Full Elimination, not Triangular . . . . . . . . . . . . . . . . . . . . . . . . 147
9.5.3 The Rank of 3k Rows, or Why k +
ε is not Enough . . . . . . . . 148
9.5.4 Using Bulk Logical Operations . . . . . . . . . . . . . . . . . . . . . . . . . 149
9.6 Experimental and Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . 149
9.7 M4RI Experiments Performed by S
AGE Staff . . . . . . . . . . . . . . . . . . . 151
9.7.1 Determination of k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
9.7.2 The Transpose Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
9.8 Pairing With Strassen’s Algorithm for Matrix Multiplication . . . . . . 151
9.8.1 Pairing M4RI with Strassen . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
9.9 Higher Values of q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
9.9.1 Building the Gray Code over GF(q) . . . . . . . . . . . . . . . . . . . . 152
9.9.2 Other Modifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
9.9.3 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
9.9.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
Contents xxi
10 The Quadratic Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
10.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
10.1.1 A View of RSA from 60,000 feet . . . . . . . . . . . . . . . . . . . . . . . 160
10.1.2 Two Facts from Number Theory . . . . . . . . . . . . . . . . . . . . . . . . 161
10.1.3 Reconstructing the Private Key from the Public Key . . . . . . . 161
10.2 Trial Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
10.2.1 Other Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
10.2.2 Sieve of Eratosthenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
10.3 Theoretical Foundations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
10.4 The Na
¨
ıve Sieve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
10.4.1 An Extended Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
10.5 The G
¨
odel Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
10.5.1 Benefits of the Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
10.5.2 Unlimited-Dimension Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 173
10.5.3 The Master Stratagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
10.5.4 Historical Interlude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
10.5.5 Review of Null Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
10.5.6 Constructing a Vector in the Even-Space . . . . . . . . . . . . . . . . . 175
10.6 The Linear Sieve Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
10.6.1 Matrix Dimensions in the Linear & Quadratic Sieve . . . . . . . 176
10.6.2 The Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
10.7 The Example, Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
10.8 Rapidly Generating Smooth Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
10.8.1 New Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
10.9 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
10.10Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Part III Polynomial Systems and Satisfiability
11 Strategies for Polynomial Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
11.1 Why Solve Polynomial Systems of Equations over Finite Fields? . . . 187
11.2 Universal Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
11.3 Polynomials over GF(2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
11.3.1 Exponents: x
2
= x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
11.3.2 Equivalent versus Identical Polynomials . . . . . . . . . . . . . . . . . 191
11.3.3 Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
11.3.4 Linear Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
11.4 Degree Reduction Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
11.4.1 An Easy but Hard-to-State Condition . . . . . . . . . . . . . . . . . . . . 193
11.4.2 An Algorithm that meets this Condition . . . . . . . . . . . . . . . . . 194
11.4.3 Interpretation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
11.4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
11.4.5 Detour: Asymptotics of the “Choose” Function . . . . . . . . . . . 196
11.4.6 Complexity Calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
11.4.7 Efficiency Note . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
xxii Contents
11.4.8 The Greedy Degree-Dropper Algorithm . . . . . . . . . . . . . . . . . 198
11.4.9 Counter-Example for Linear Systems . . . . . . . . . . . . . . . . . . . 199
11.5 NP-Completeness of MP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
11.6 Measures of Difficulty in MQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
11.6.1 The Role of Over-Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
11.6.2 Ultra-Sparse Quadratic Systems . . . . . . . . . . . . . . . . . . . . . . . . 203
11.6.3 Other Views of Sparsity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
11.6.4 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
11.7 The Role of Guessing a Few Variables . . . . . . . . . . . . . . . . . . . . . . . . . 206
11.7.1 Measuring Infeasible Running Times . . . . . . . . . . . . . . . . . . . . 206
11.7.2 Fix-XL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12 Algorithms for Solving Polynomial Systems . . . . . . . . . . . . . . . . . . . . . . . 209
12.1 A Philosophical Point on Complexity Theory . . . . . . . . . . . . . . . . . . . 209
12.2 Gr
¨
obner Bases Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
12.2.1 Double-Exponential Running Time . . . . . . . . . . . . . . . . . . . . . 210
12.2.2 Remarks about Gr
¨
obner Bases . . . . . . . . . . . . . . . . . . . . . . . . . 210
12.3 Linearization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
12.4 The XL Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
12.4.1 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
12.4.2 Sufficiently Many Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
12.4.3 Jumping Two Degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
12.4.4 Fix-XL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
12.5 ElimLin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
12.5.1 Why is this useful? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
12.5.2 How to use ElimLin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
12.5.3 On the Sub-Space of Linear Equations in the Span of a
Quadratic System of Equations . . . . . . . . . . . . . . . . . . . . . . . . . 223
12.5.4 The Weight of the Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
12.5.5 One Last Trick for GF(2)-only . . . . . . . . . . . . . . . . . . . . . . . . . 225
12.5.6 Notes on the Sufficient Rank Condition . . . . . . . . . . . . . . . . . . 226
12.6 Comparisons between XL and F4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
12.7 SAT-Solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
12.8 System Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
12.8.1 Separability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
12.8.2 Gaussian Elimination is Not Enough . . . . . . . . . . . . . . . . . . . . 230
12.8.3 Depth First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
12.8.4 Nearly Separable Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
12.8.5 Removing Multiple vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
12.8.6 Relation to Menger’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 232
12.8.7 Balance in Vertex Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
12.8.8 Applicability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
12.9 Resultants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
12.9.1 The Univariate Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
12.9.2 The Bivariate Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
剩余369页未读,继续阅读
2023-06-06 上传
2023-08-13 上传
2023-08-13 上传
2023-06-06 上传
2021-12-15 上传
2023-08-12 上传
2023-05-26 上传
Alice?Bob
- 粉丝: 16
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 掌握压缩文件管理:2工作.zip文件使用指南
- 易语言动态版置入代码技术解析
- C语言编程实现电脑系统测试工具开发
- Wireshark 64位:全面网络协议分析器,支持Unix和Windows
- QtSingleApplication: 确保单一实例运行的高效库
- 深入了解Go语言的解析器组合器PARC
- Apycula包安装与使用指南
- AkerAutoSetup安装包使用指南
- Arduino Due实现VR耳机的设计与编程
- DependencySwizzler: Xamarin iOS 库实现故事板 UIViewControllers 依赖注入
- Apycula包发布说明与下载指南
- 创建可拖动交互式图表界面的ampersand-touch-charts
- CMake项目入门:创建简单的C++项目
- AksharaJaana-*.*.*.*安装包说明与下载
- Arduino天气时钟项目:源代码及DHT22库文件解析
- MediaPlayer_server:控制媒体播放器的高级服务器
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功