Finite Fields and Their Applications

1 - Preface [Seite 5]
2 - Character Sums and Polyphase Sequence Families with Low Correlation, Discrete Fourier Transform (DFT), and Ambiguity [Seite 13]
2.1 - 1 Introduction [Seite 13]
2.2 - 2 Basic Definitions and Concepts [Seite 14]
2.2.1 - 2.1 Notations [Seite 14]
2.2.2 - 2.2 Polynomial Functions over Fq [Seite 15]
2.2.3 - 2.3 Characters of Finite Fields [Seite 16]
2.2.4 - 2.4 The Weil Bounds on Character Sums [Seite 16]
2.3 - 3 Correlation, DFT, and Ambiguity Functions [Seite 17]
2.3.1 - 3.1 Operators on Sequences [Seite 17]
2.3.2 - 3.2 Correlation Functions [Seite 18]
2.3.3 - 3.3 Ambiguity Functions [Seite 20]
2.3.4 - 3.4 Convolution and Correlation [Seite 22]
2.3.5 - 3.5 Optimal Correlation, DFT, and Ambiguity [Seite 22]
2.4 - 4 Polyphase Sequences for Three Metrics [Seite 23]
2.4.1 - 4.1 Sequences from the Additive Group of ZN and the Additive Group of Zp [Seite 23]
2.4.1.1 - 4.1.1 Frank-Zadoff-Chu (FZC) Sequences [Seite 23]
2.4.1.2 - 4.1.2 Another Class for Zn [Seite 25]
2.4.1.3 - 4.1.3 Sequences from Fp Additive Characters [Seite 25]
2.4.2 - 4.2 Sequences from Fp Multiplicative Characters [Seite 25]
2.4.3 - 4.3 Sequences from Fq Additive Characters [Seite 27]
2.4.4 - 4.4 Sequences from Fq Multiplicative Characters [Seite 29]
2.4.5 - 4.5 Sequences Defined by Indexing Field Elements Alternatively [Seite 32]
2.5 - 5 Sequences with Low Degree Polynomials [Seite 34]
2.5.1 - 5.1 Methods for Generating Signal Sets from a Single Sequence [Seite 34]
2.5.2 - 5.2 Sequences with Low Odd Degree Polynomials [Seite 35]
2.5.2.1 - 5.2.1 Fq Additive Sequences with Low Odd Degree Polynomials [Seite 35]
2.5.2.2 - 5.2.2 Fq Multiplicative Sequences with Low Odd Degree Polynomials [Seite 37]
2.5.3 - 5.3 Sequences from Power Residue and Sidel'nikov Sequences [Seite 38]
2.5.3.1 - 5.3.1 Interleaved Structure of Sidel'nikov Sequences [Seite 38]
2.5.3.2 - 5.3.2 Sequences from Linear and/or Quadratic/Inverse Polynomials [Seite 39]
2.5.4 - 5.4 Sequences from Hybrid Characters [Seite 41]
2.5.4.1 - 5.4.1 Sequences Using Weil Representation and Their Generalizations [Seite 41]
2.5.4.2 - 5.4.2 Generalization to Fq Hybrid Sequences [Seite 42]
2.5.5 - 5.5 A New Construction [Seite 44]
2.6 - 6 Two-Level Autocorrelation Sequences and Double Exponential Sums [Seite 45]
2.6.1 - 6.1 Prime Two-Level Autocorrelation Sequences [Seite 45]
2.6.2 - 6.2 Hadamard Transform, Second-Order Decimation-Hadamard Transform, and Hadamard Equivalence [Seite 46]
2.6.3 - 6.3 Conjectures on Ternary 2-Level Autocorrelation Sequences [Seite 47]
2.7 - 7 Some Open Problems [Seite 49]
2.7.1 - 7.1 Current Status of the Conjectures on Ternary 2-Level Autocorrelation [Seite 49]
2.7.2 - 7.2 Possibility of Multiplicative Sequences with Low Autocorrelation [Seite 50]
2.7.3 - 7.3 Problems in Four Alternative Classes of Sequences and the General Hybrid Construction [Seite 50]
2.8 - 8 Conclusions [Seite 50]
3 - Measures of Pseudorandomness [Seite 55]
3.1 - 1 Introduction [Seite 55]
3.2 - 2 Definition of the Pseudorandom Measures [Seite 56]
3.3 - 3 Typical Values of Pseudorandom Measures [Seite 58]
3.4 - 4 Minimum Values of Pseudorandom Measures [Seite 59]
3.5 - 5 Connection between Pseudorandom Measures [Seite 61]
3.6 - 6 Constructions [Seite 62]
3.7 - 7 Family Measures [Seite 64]
3.8 - 8 Linear Complexity [Seite 66]
3.9 - 9 Multidimensional Theory [Seite 68]
3.10 - 10 Extensions [Seite 69]
4 - Existence Results for Finite Field Polynomials with Specified Properties [Seite 77]
4.1 - 1 Introduction [Seite 77]
4.2 - 2 A Survey of Known Results [Seite 78]
4.2.1 - 2.1 Normal Bases [Seite 79]
4.2.2 - 2.2 Primitive Normal Bases [Seite 80]
4.2.3 - 2.3 Prescribed Coefficients [Seite 82]
4.2.4 - 2.4 Primitive Polynomials: Prescribed Coefficients [Seite 82]
4.2.5 - 2.5 Primitive Normal Polynomials: Prescribed Coefficients [Seite 85]
4.3 - 3 A Survey of Methodology and Techniques [Seite 87]
4.3.1 - 3.1 Basic Approach [Seite 88]
4.3.2 - 3.2 A p-adic Approach to Coefficient Constraints [Seite 90]
4.3.3 - 3.3 The Sieving Technique [Seite 93]
4.4 - 4 Conclusion [Seite 95]
5 - Incidence Structures, Codes, and Galois Geometries [Seite 101]
5.1 - 1 Introduction [Seite 101]
5.2 - 2 Galois Closed Codes [Seite 103]
5.3 - 3 Extension Codes of Simplex and First-Order Reed-Muller Codes [Seite 105]
5.4 - 4 Simple Incidence Structures and Their Codes [Seite 109]
5.5 - 5 Embedding Theorems [Seite 111]
5.6 - 6 Designs with Classical Parameters [Seite 117]
5.7 - 7 Two-Weight Codes [Seite 120]
5.8 - 8 Steiner Systems [Seite 121]
5.9 - 9 Configurations [Seite 123]
5.10 - 10 Conclusion and Open Problems [Seite 125]
6 - Special Mappings of Finite Fields [Seite 129]
6.1 - 1 Introduction [Seite 129]
6.2 - 2 Different Notions for Optimal Non-linearity [Seite 132]
6.2.1 - 2.1 Almost Perfect Nonlinear (APN) Mappings [Seite 133]
6.2.2 - 2.2 Bent and Almost Bent (AB) Mappings [Seite 136]
6.3 - 3 Functions with a Linear Structure [Seite 137]
6.4 - 4 Crooked Mappings [Seite 140]
6.5 - 5 Planar Mappings [Seite 142]
6.6 - 6 Switching Construction [Seite 145]
6.7 - 7 Products of Linearized Polynomials [Seite 149]
7 - On The Classification of Perfect Nonlinear (PN) and Almost Perfect Nonlinear (APN) Monomial Functions [Seite 157]
7.1 - 1 Introduction [Seite 157]
7.2 - 2 Background and Motivation [Seite 158]
7.2.1 - 2.1 PN and Planar Functions [Seite 158]
7.2.2 - 2.2 APN Functions [Seite 160]
7.3 - 3 Outline of APN Functions Classification Proof [Seite 161]
7.3.1 - 3.1 Singularities in APN case [Seite 163]
7.3.2 - 3.2 A Warm-Up Case [Seite 165]
7.4 - 4 PN Functions Classification Proof: Analysis of Singularities [Seite 166]
7.4.1 - 4.1 Singular Points in Case (b.1) [Seite 168]
7.4.2 - 4.2 Singular Points at Infinity [Seite 169]
7.4.3 - 4.3 The Multiplicities [Seite 171]
7.4.4 - 4.4 Further Analysis [Seite 171]
7.4.5 - 4.5 Type(i) [Seite 173]
7.4.6 - 4.6 Type(iii) [Seite 173]
7.4.7 - 4.7 Type(ii) [Seite 173]
7.5 - 5 Case (b.1): Assuming Bt(x,y) Irreducible over Fp [Seite 174]
7.6 - 6 Case (b.1): Assuming Bt (x, y) not Irreducible over Fp [Seite 176]
8 - Finite Fields and Quasirandom Points [Seite 181]
8.1 - 1 Introduction [Seite 181]
8.2 - 2 General Background [Seite 182]
8.3 - 3 General Construction Principles [Seite 185]
8.4 - 4 The Combinatorics of Nets [Seite 189]
8.5 - 5 Duality Theory [Seite 191]
8.6 - 6 Special Constructions of Nets [Seite 193]
8.6.1 - 6.1 Polynomial Lattices [Seite 193]
8.6.2 - 6.2 Hyperplane Nets [Seite 195]
8.6.3 - 6.3 Nets Obtained from Global Function Fields [Seite 197]
8.7 - 7 Special Constructions of (T,s)-Sequences [Seite 199]
8.7.1 - 7.1 Faure Sequences and Niederreiter Sequences-c [Seite 200]
8.7.2 - 7.2 Sequences Obtained from Global Function Fields [Seite 201]
8.7.3 - 7.3 Sequences with Finite-Row Generating Matrices [Seite 204]
9 - Iterations of Rational Functions: Some Algebraic and Arithmetic Aspects [Seite 209]
9.1 - 1 Introduction [Seite 209]
9.1.1 - 1.1 Background [Seite 209]
9.1.2 - 1.2 Notation [Seite 210]
9.1.3 - 1.3 Iterations [Seite 210]
9.2 - 2 Distribution of Elements, Degree Growth and Representation [Seite 211]
9.2.1 - 2.1 Exponential Sums and Linear Combinations of Iterates [Seite 211]
9.2.2 - 2.2 Generic Multivariate Polynomials [Seite 213]
9.2.3 - 2.3 Systems with Slow Degree Growth [Seite 215]
9.2.4 - 2.4 Exponential Degree Growth, but Sparse Representation [Seite 218]
9.2.5 - 2.5 Representation of Iterates [Seite 219]
9.2.6 - 2.6 Deligne and Dwork-Regular Polynomials [Seite 220]
9.2.7 - 2.7 Distribution in Prime and Polynomial Times [Seite 221]
9.3 - 3 Structure of Rational Function Maps [Seite 222]
9.3.1 - 3.1 Trajectory Length and Periodic Structure [Seite 222]
9.3.2 - 3.2 Graph of Rational Function Maps [Seite 224]
9.3.3 - 3.3 Common Composites and Intersection of Orbits [Seite 225]
9.4 - 4 Geometric Properties of Orbits [Seite 227]
9.4.1 - 4.1 Diameter of Orbits [Seite 227]
9.4.2 - 4.2 Convex Hull of Trajectories [Seite 229]
9.5 - 5 Stability, Absolute Irreducibility and Coprimality [Seite 229]
9.5.1 - 5.1 Motivation [Seite 229]
9.5.2 - 5.2 Stable Univariate Polynomials [Seite 230]
9.5.3 - 5.3 On the Growth of the Number of Irreducible Factors [Seite 232]
9.5.4 - 5.4 Stable Multivariate Polynomials [Seite 234]
9.5.5 - 5.5 Coprimality of Iterates [Seite 236]
9.6 - 6 More Problems [Seite 236]
9.6.1 - 6.1 Multiplicative Independence [Seite 236]
9.6.2 - 6.2 Complete Polynomials [Seite 237]
10 - Additive Combinatorics over Finite Fields: New Results and Applications [Seite 245]
10.1 - 1 Introduction [Seite 245]
10.2 - 2 Notation [Seite 247]
10.3 - 3 Estimates from Arithmetic Combinatorics [Seite 248]
10.3.1 - 3.1 Classical Sum-Product Problem [Seite 248]
10.3.2 - 3.2 Multifold Sum-Product Problem [Seite 250]
10.3.3 - 3.3 Sum-Inversion Estimates [Seite 251]
10.3.4 - 3.4 Equations over Finite Fields with Variables from Arbitrary Sets [Seite 253]
10.3.5 - 3.5 Incidence Bounds [Seite 255]
10.3.6 - 3.6 Polynomial and Other Nonlinear Functions on Sets [Seite 257]
10.3.7 - 3.7 Structured Sets [Seite 259]
10.3.8 - 3.8 Elliptic Curve Analogues [Seite 261]
10.3.9 - 3.9 Matrix Analogues [Seite 264]
10.4 - 4 Applications [Seite 265]
10.4.1 - 4.1 Exponential and Character Sums [Seite 265]
10.4.2 - 4.2 Waring, Erdos-Graham and Other Additive Problems in Finite Fields [Seite 268]
10.4.3 - 4.3 Intersections of Almost Arithmetic and Geometric Progressions [Seite 270]
10.4.4 - 4.4 Exponential Congruence [Seite 272]
10.4.5 - 4.5 Hidden Shifted Power Problem [Seite 273]
10.4.6 - Sum-Product Estimates and Multiplicative Orders of . and . + .-1 in Finite Fields [Seite 273]
10.4.7 - 4.7 Expansion of Dynamical Systems [Seite 274]