Finite Fields and Their Applications (eBook)

lt;!doctype html public "-//w3c//dtd html 4.0 transitional//en">

Pascale Charpin, INRIA, Le Chesnay, France;Alexander Pott, Otto-von-Guericke-University Magdeburg, Germany; Arne Winterhof, Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Linz, Austria.

Preface 5
Character Sums and Polyphase Sequence Families with Low Correlation, Discrete Fourier Transform (DFT), and Ambiguity 13
1 Introduction 13
2 Basic Definitions and Concepts 14
2.1 Notations 14
2.2 Polynomial Functions over Fq 15
2.3 Characters of Finite Fields 16
2.4 The Weil Bounds on Character Sums 16
3 Correlation, DFT, and Ambiguity Functions 17
3.1 Operators on Sequences 17
3.2 Correlation Functions 18
3.3 Ambiguity Functions 20
3.4 Convolution and Correlation 22
3.5 Optimal Correlation, DFT, and Ambiguity 22
4 Polyphase Sequences for Three Metrics 23
4.1 Sequences from the Additive Group of ZN and the Additive Group of Zp 23
4.1.1 Frank-Zadoff-Chu (FZC) Sequences 23
4.1.2 Another Class for Zn 25
4.1.3 Sequences from Fp Additive Characters 25
4.2 Sequences from Fp Multiplicative Characters 25
4.3 Sequences from Fq Additive Characters 27
4.4 Sequences from Fq Multiplicative Characters 29
4.5 Sequences Defined by Indexing Field Elements Alternatively 32
5 Sequences with Low Degree Polynomials 34
5.1 Methods for Generating Signal Sets from a Single Sequence 34
5.2 Sequences with Low Odd Degree Polynomials 35
5.2.1 Fq Additive Sequences with Low Odd Degree Polynomials 35
5.2.2 Fq Multiplicative Sequences with Low Odd Degree Polynomials 37
5.3 Sequences from Power Residue and Sidel’nikov Sequences 38
5.3.1 Interleaved Structure of Sidel’nikov Sequences 38
5.3.2 Sequences from Linear and/or Quadratic/Inverse Polynomials 39
5.4 Sequences from Hybrid Characters 41
5.4.1 Sequences Using Weil Representation and Their Generalizations 41
5.4.2 Generalization to Fq Hybrid Sequences 42
5.5 A New Construction 44
6 Two-Level Autocorrelation Sequences and Double Exponential Sums 45
6.1 Prime Two-Level Autocorrelation Sequences 45
6.2 Hadamard Transform, Second-Order Decimation-Hadamard Transform, and Hadamard Equivalence 46
6.3 Conjectures on Ternary 2-Level Autocorrelation Sequences 47
7 Some Open Problems 49
7.1 Current Status of the Conjectures on Ternary 2-Level Autocorrelation 49
7.2 Possibility of Multiplicative Sequences with Low Autocorrelation 50
7.3 Problems in Four Alternative Classes of Sequences and the General Hybrid Construction 50
8 Conclusions 50
Measures of Pseudorandomness 55
1 Introduction 55
2 Definition of the Pseudorandom Measures 56
3 Typical Values of Pseudorandom Measures 58
4 Minimum Values of Pseudorandom Measures 59
5 Connection between Pseudorandom Measures 61
6 Constructions 62
7 Family Measures 64
8 Linear Complexity 66
9 Multidimensional Theory 68
10 Extensions 69
Existence Results for Finite Field Polynomials with Specified Properties 77
1 Introduction 77
2 A Survey of Known Results 78
2.1 Normal Bases 79
2.2 Primitive Normal Bases 80
2.3 Prescribed Coefficients 82
2.4 Primitive Polynomials: Prescribed Coefficients 82
2.5 Primitive Normal Polynomials: Prescribed Coefficients 85
3 A Survey of Methodology and Techniques 87
3.1 Basic Approach 88
3.2 A p-adic Approach to Coefficient Constraints 90
3.3 The Sieving Technique 93
4 Conclusion 95
Incidence Structures, Codes, and Galois Geometries 101
1 Introduction 101
2 Galois Closed Codes 103
3 Extension Codes of Simplex and First-Order Reed-Muller Codes 105
4 Simple Incidence Structures and Their Codes 109
5 Embedding Theorems 111
6 Designs with Classical Parameters 117
7 Two-Weight Codes 120
8 Steiner Systems 121
9 Configurations 123
10 Conclusion and Open Problems 125
Special Mappings of Finite Fields 129
1 Introduction 129
2 Different Notions for Optimal Non-linearity 132
2.1 Almost Perfect Nonlinear (APN) Mappings 133
2.2 Bent and Almost Bent (AB) Mappings 136
3 Functions with a Linear Structure 137
4 Crooked Mappings 140
5 Planar Mappings 142
6 Switching Construction 145
7 Products of Linearized Polynomials 149
On The Classification of Perfect Nonlinear (PN) and Almost Perfect Nonlinear (APN) Monomial Functions 157
1 Introduction 157
2 Background and Motivation 158
2.1 PN and Planar Functions 158
2.2 APN Functions 160
3 Outline of APN Functions Classification Proof 161
3.1 Singularities in APN case 163
3.2 A Warm-Up Case 165
4 PN Functions Classification Proof: Analysis of Singularities 166
4.1 Singular Points in Case (b.1) 168
4.2 Singular Points at Infinity 169
4.3 The Multiplicities 171
4.4 Further Analysis 171
4.5 Type(i) 173
4.6 Type(iii) 173
4.7 Type(ii) 173
5 Case (b.1): Assuming Bt(x,y) Irreducible over Fp 174
6 Case (b.1): Assuming Bt (x, y) not Irreducible over Fp 176
Finite Fields and Quasirandom Points 181
1 Introduction 181
2 General Background 182
3 General Construction Principles 185
4 The Combinatorics of Nets 189
5 Duality Theory 191
6 Special Constructions of Nets 193
6.1 Polynomial Lattices 193
6.2 Hyperplane Nets 195
6.3 Nets Obtained from Global Function Fields 197
7 Special Constructions of (T,s)-Sequences 199
7.1 Faure Sequences and Niederreiter Sequences-c 200
7.2 Sequences Obtained from Global Function Fields 201
7.3 Sequences with Finite-Row Generating Matrices 204
Iterations of Rational Functions: Some Algebraic and Arithmetic Aspects 209
1 Introduction 209
1.1 Background 209
1.2 Notation 210
1.3 Iterations 210
2 Distribution of Elements, Degree Growth and Representation 211
2.1 Exponential Sums and Linear Combinations of Iterates 211
2.2 Generic Multivariate Polynomials 213
2.3 Systems with Slow Degree Growth 215
2.4 Exponential Degree Growth, but Sparse Representation 218
2.5 Representation of Iterates 219
2.6 Deligne and Dwork-Regular Polynomials 220
2.7 Distribution in Prime and Polynomial Times 221
3 Structure of Rational Function Maps 222
3.1 Trajectory Length and Periodic Structure 222
3.2 Graph of Rational Function Maps 224
3.3 Common Composites and Intersection of Orbits 225
4 Geometric Properties of Orbits 227
4.1 Diameter of Orbits 227
4.2 Convex Hull of Trajectories 229
5 Stability, Absolute Irreducibility and Coprimality 229
5.1 Motivation 229
5.2 Stable Univariate Polynomials 230
5.3 On the Growth of the Number of Irreducible Factors 232
5.4 Stable Multivariate Polynomials 234
5.5 Coprimality of Iterates 236
6 More Problems 236
6.1 Multiplicative Independence 236
6.2 Complete Polynomials 237
Additive Combinatorics over Finite Fields: New Results and Applications 245
1 Introduction 245
2 Notation 247
3 Estimates from Arithmetic Combinatorics 248
3.1 Classical Sum-Product Problem 248
3.2 Multifold Sum-Product Problem 250
3.3 Sum-Inversion Estimates 251
3.4 Equations over Finite Fields with Variables from Arbitrary Sets 253
3.5 Incidence Bounds 255
3.6 Polynomial and Other Nonlinear Functions on Sets 257
3.7 Structured Sets 259
3.8 Elliptic Curve Analogues 261
3.9 Matrix Analogues 264
4 Applications 265
4.1 Exponential and Character Sums 265
4.2 Waring, Erdos-Graham and Other Additive Problems in Finite Fields 268
4.3 Intersections of Almost Arithmetic and Geometric Progressions 270
4.4 Exponential Congruence 272
4.5 Hidden Shifted Power Problem 273
Sum-Product Estimates and Multiplicative Orders of . and . + .-1 in Finite Fields 273
4.7 Expansion of Dynamical Systems 274