2009年Gregory V. Bard的代数密码学论文集

需积分: 11 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 Deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Modiﬁcations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Beneﬁts 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 Satisﬁability

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

= x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

11.3.2 Equivalent versus Identical Polynomials . . . . . . . . . . . . . . . . . 191

11.3.3 Coefﬁcients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Efﬁciency 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 Difﬁculty in MQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

11.6.1 The Role of Over-Deﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Sufﬁciently 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 Sufﬁcient 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页未读，继续阅读

Alice?Bob

粉丝: 16
资源: 1

2009年Gregory V. Bard的代数密码学论文集

Algebraic Cryptanalysis

计算机行业周报：谷歌推出AI聊天机器人Bard测试版本.pdf

抢先微软，Google版Copilot上线！谷歌宣布给Google全家桶开放Bard功能.pdf

Itbhacker 对比Bard VS Chat(1)(8).pdf

谷歌 Bard 大升级超越 ChatGPT：这 10 个功能 ChatGPT 也做不到.pdf

人工智能-谷歌发布Bard模型，微软Bing浏览器内置类ChatGPT技术-230212.pdf

【友谊是巫术】Gypsy Bard (Gb's Remix)钢琴曲谱数字简谱.pdf

领英职场退出中国，谷歌Bard集成进安卓，陆奇最新演讲，HuggingFace网传遭禁｜今日科技圈要闻.pdf

传媒-ChatGPT持续出圈，生成式AI迎来拐点，关注微软-谷歌-百度布局.pdf.zip

Bard

最新资源