Charpin / Pott / Winterhof Finite Fields and Their Applications

Character Sums and Polynomials
1. Auflage 2013
ISBN: 978-3-11-028360-0
Verlag: De Gruyter
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, Band 11, 285 Seiten

Reihe: Radon Series on Computational and Applied Mathematics

Zielgruppe

Researchers, Lecturers, and Graduate Students in Mathematics, e.g

Autoren/Hrsg.

Charpin, Pascale

Pott, Alexander

Winterhof, Arne

Weitere Mitwirkende

Gong, Guang

Gyarmati, Katalin

Hernando, Fernando

Huczynska, Sophie

Jungnickel, Dieter

Kyureghyan, Gohar M.

McGuire, Gary

Niederreiter, Harald

Ostafe, Alina

Shparlinski, Igor E.

Fachgebiete

• Interdisziplinäres Wissenschaften Wissenschaften: Forschung und Information Informationstheorie, Kodierungstheorie
• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
• Mathematik | Informatik Mathematik Algebra Algebraische Strukturen, Gruppentheorie
• Mathematik | Informatik EDV | Informatik Daten / Datenbanken Informationstheorie, Kodierungstheorie

Inhaltsverzeichnis

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

Über Autor(innen)

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.