Muutke küpsiste eelistusi

Handbook of Finite Fields [Kõva köide]

(Pennsylvania State University, University Park, USA), (Carleton University, Ottawa, Ontario, Canada)
  • Formaat: Hardback, 1070 pages, kõrgus x laius: 254x178 mm, kaal: 1814 g, 40 Tables, black and white; 12 Illustrations, black and white
  • Sari: Discrete Mathematics and Its Applications
  • Ilmumisaeg: 17-Jun-2013
  • Kirjastus: Chapman & Hall/CRC
  • ISBN-10: 143987378X
  • ISBN-13: 9781439873786
Teised raamatud teemal:
Handbook of Finite FieldsSuurem pilt
  • Formaat: Hardback, 1070 pages, kõrgus x laius: 254x178 mm, kaal: 1814 g, 40 Tables, black and white; 12 Illustrations, black and white
  • Sari: Discrete Mathematics and Its Applications
  • Ilmumisaeg: 17-Jun-2013
  • Kirjastus: Chapman & Hall/CRC
  • ISBN-10: 143987378X
  • ISBN-13: 9781439873786
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781439873786.html
Märksõnad:
"Poised to become the leading reference in the field, the Handbook of Finite Fields is exclusively devoted to the theory and applications of finite fields. More than 80 international contributors compile state-of-the-art research in this definitive handbook. Edited by two renowned researchers, the book uses a uniform style and format throughout and each chapter is self contained and peer reviewed. The first part of the book traces the history of finite fields through the eighteenth and nineteenth centuries. The second part presents theoretical properties of finite fields, covering polynomials, special functions, sequences, algorithms, curves, and related computational aspects. The final part describes various mathematical and practical applications of finite fields in combinatorics, algebraic coding theory, cryptographic systems, biology, quantum information theory, engineering, and other areas. The book provides a comprehensive index and easy access to over 3,000 references, enabling you to quickly locate up-to-date facts and results regarding finite fields"--

"Preface The CRC Handbook of Finite Fields (hereafter referred to as the Handbook) is a reference book for the theory and applications of nite elds. It is not intended to be an introductory textbook. Our goal is to compile in one volume the state of the art in research in nite elds and their applications. Hence, our aim is a comprehensive book, with easy-to-access references for up-to-date facts and results regarding nite elds. The Handbook is organized into three parts. Part I contains just one chapter which is devoted to the history of nite elds through the 18-th and 19-th centuries. Part II contains theoretical properties of nite elds. This part of the Handbook contains 12 chapters. Chapter 2 deals with basic properties of nite elds; properties that are used in various places throughout the entire Handbook. Near the end of Section 2.1 is a rather extensive list of recent nite eld-related books; these books include textbooks, books dealing with theoretical topics as well as books dealing with various applications to such topics as combinatorics, algebraic coding theory for the error-free transmission of information, and cryptography for the secure transmission of information. Also included is a list of recent nite eld-related conference proceedings volumes. Chapter 2 also provides rather extensive tables of polynomials useful when dealing with nite eld computational issues. The website http://www.crcpress.com/product/isbn/ 9781439873786 provides larger and more extensive versions of the tables presented in Section"--

Poised to become the leading reference in the field, the Handbook of Finite Fields is exclusively devoted to the theory and applications of finite fields. More than 80 international contributors compile state-of-the-art research in this definitive handbook. Edited by two renowned researchers, the book uses a uniform style and format throughout and each chapter is self contained and peer reviewed.

The first part of the book traces the history of finite fields through the eighteenth and nineteenth centuries. The second part presents theoretical properties of finite fields, covering polynomials, special functions, sequences, algorithms, curves, and related computational aspects. The final part describes various mathematical and practical applications of finite fields in combinatorics, algebraic coding theory, cryptographic systems, biology, quantum information theory, engineering, and other areas. The book provides a comprehensive index and easy access to over 3,000 references, enabling you to quickly locate up-to-date facts and results regarding finite fields.

Arvustused

"... a brilliant, monumental work on the state of the art in theory and applications of finite fields. It's a must for everyone doing research in finite fields and their related areas. ... It presents such a huge amount of information readily available and masterly presented. Editors, contributors, and the publisher are equally congratulated for providing such a beautiful result not only for the finite field community, but also for those from the applied areas, especially cryptographers and coding theorists." Olaf Ninnemann, Berlin, in Zentralblatt MATH 1319

"The handbook will be very useful for senior-level students, teachers, and researchers in mathematics and computer science. It will also be useful for scientists, engineers, and practitioners. The handbook is well organized. ... It is likely to become a standard reference book for the theory and applications of finite fields. ... It will be a very useful addition to the libraries of academic and research institutions." S.V.Nagaraj, Chennai, India, in SIGACT News

Part I Introduction
1 History of finite fields
3(10)
1.1 Finite fields in the 18-th and 19-th centuries
3(10)
Roderick Gow
1.1.1 Introduction
3(1)
1.1.2 Early anticipations of finite fields
4(1)
1.1.3 Gauss's Disquisitiones Arithmeticae
4(1)
1.1.4 Gauss's Disquisitiones Generales de Congruentiis
5(1)
1.1.5 Galois's Sur la theorie des nombres
6(2)
1.1.6 Serret's Cours d'Algebre superieure
8(1)
1.1.7 Contributions of Schonemann and Dedekind
9(1)
1.1.8 Moore's characterization of abstract finite fields
10(1)
1.1.9 Later developments
10(3)
2 Introduction to finite fields
13(40)
2.1 Basic properties of finite fields
13(19)
Gary L. Mullen
Daniel Panario
2.1.1 Basic definitions
13(1)
2.1.2 Fundamental properties of finite fields
14(4)
2.1.3 Extension fields
18(2)
2.1.4 Trace and norm functions
20(1)
2.1.5 Bases
21(2)
2.1.6 Linearized polynomials
23(1)
2.1.7 Miscellaneous results
23(1)
2.1.7.1 The finite field polynomial Φ function
24(1)
2.1.7.2 Cyclotomic polynomials
24(2)
2.1.7.3 Lagrange interpolation
26(1)
2.1.7.4 Discriminants
26(1)
2.1.7.5 Jacobi logarithms
27(1)
2.1.7.6 Field-like structures
27(1)
2.1.7.7 Galois rings
28(3)
2.1.8 Finite field related books
31(1)
2.1.8.1 Textbooks
31(1)
2.1.8.2 Finite field theory
31(1)
2.1.8.3 Applications
31(1)
2.1.8.4 Algorithms
31(1)
2.1.8.5 Conference proceedings
31(1)
2.2 Tables David Thomson
32(21)
2.2.1 Low-weight irreducible and primitive polynomials
32(5)
2.2.2 Low-complexity normal bases
37(1)
2.2.2.1 Exhaustive search for low complexity normal bases
38(2)
2.2.2.2 Minimum type of a Gauss period admitting a normal basis of F2n, over F2
40(1)
2.2.2.3 Minimum-known complexity of a normal basis of F2n over F2, n ≥40
41(5)
2.2.3 Resources and standards
46(7)
Part II Theoretical Properties
3 Irreducible polynomials
53(34)
3.1 Counting irreducible polynomials
53(7)
Joseph L. Yucas
3.1.1 Prescribed trace or norm
54(1)
3.1.2 Prescribed coefficients over the binary field
55(1)
3.1.3 Self-reciprocal polynomials
56(1)
3.1.4 Compositions of powers
57(1)
3.1.5 Translation invariant polynomials
58(1)
3.1.6 Normal replicators
58(2)
3.2 Construction of irreducibles
60(6)
Melsik Kyuregyan
3.2.1 Construction by composition
60(3)
3.2.2 Recursive constructions
63(3)
3.3 Conditions for reducible polynomials
66(4)
Daniel Panario
3.3.1 Composite polynomials
66(1)
3.3.2 Swan-type theorems
67(3)
3.4 Weights of irreducible polynomials
70(3)
Omran Ahmadi
3.4.1 Basic definitions
70(1)
3.4.2 Existence results
70(2)
3.4.3 Conjectures
72(1)
3.5 Prescribed coefficients
73(7)
Stephen D. Cohen
3.5.1 One prescribed coefficient
74(1)
3.5.2 Prescribed trace and norm
75(1)
3.5.3 More prescribed coefficients
76(2)
3.5.4 Further exact expressions
78(2)
3.6 Multivariate polynomials
80(7)
Xiang-dong Hou
3.6.1 Counting formulas
80(1)
3.6.2 Asymptotic formulas
81(1)
3.6.3 Results for the vector degree
81(2)
3.6.4 Indecomposable polynomials and irreducible polynomials
83(1)
3.6.5 Algorithms for the gcd of multivariate polynomials
84(3)
4 Primitive polynomials
87(14)
4.1 Introduction to primitive polynomials
87(3)
Gary L. Mullen
Daniel Panario
4.2 Prescribed coefficients
90(5)
Stephen D. Cohen
4.2.1 Approaches to results on prescribed coefficients
91(1)
4.2.2 Existence theorems for primitive polynomials
92(1)
4.2.3 Existence theorems for primitive normal polynomials
93(2)
4.3 Weights of primitive polynomials
95(3)
Stephen D. Cohen
4.4 Elements of high order
98(3)
Jose Felipe Voloch
4.4.1 Elements of high order from elements of small orders
98(1)
4.4.2 Gao's construction and a generalization
98(1)
4.4.3 Iterative constructions
99(2)
5 Bases
101(38)
5.1 Duality theory of bases
101(8)
Dieter Jungnickel
5.1.1 Dual bases
101(2)
5.1.2 Self-dual bases
103(1)
5.1.3 Weakly self-dual bases
104(2)
5.1.4 Binary bases with small excess
106(1)
5.1.5 Almost weakly self-dual bases
107(2)
5.1.6 Connections to hardware design
109(1)
5.2 Normal bases
109(8)
Shuhong Gao
Qunying Liao
5.2.1 Basics on normal bases
110(4)
5.2.2 Self-dual normal bases
114(1)
5.2.3 Primitive normal bases
115(2)
5.3 Complexity of normal bases
117(11)
Shuhong Gao
David Thomson
5.3.1 Optimal and low complexity normal bases
117(3)
5.3.2 Gauss periods
120(1)
5.3.3 Normal bases from elliptic periods
121(2)
5.3.4 Complexities of dual and self-dual normal bases
123(2)
5.3.4.1 Duals of Gauss periods
125(1)
5.3.5 Fast arithmetic using normal bases
125(3)
5.4 Completely normal bases
128(11)
Dirk Hachenberger
5.4.1 The complete normal basis theorem
128(2)
5.4.2 The class of completely basic extensions
130(1)
5.4.3 Cyclotomic modules and complete generators
131(2)
5.4.4 A decomposition theory for complete generators
133(1)
5.4.5 The class of regular extensions
134(1)
5.4.6 Complete generators for regular cyclotomic modules
135(2)
5.4.7 Towards a primitive complete normal basis theorem
137(2)
6 Exponential and character sums
139(54)
6.1 Gauss, Jacobi, and Kloosterman sums
139(22)
Ronald J. Evans
6.1.1 Properties of Gauss and Jacobi sums of general order
139(9)
6.1.2 Evaluations of Jacobi and Gauss sums of small orders
148(3)
6.1.3 Prime ideal divisors of Gauss and Jacobi sums
151(3)
6.1.4 Kloosterman sums
154(5)
6.1.5 Gauss and Kloosterman sums over finite rings
159(2)
6.2 More general exponential and character sums
161(9)
Antonio Rojas-Leon
6.2.1 One variable character sums
161(1)
6.2.2 Additive character sums
162(4)
6.2.3 Multiplicative character sums
166(1)
6.2.4 Generic estimates
167(1)
6.2.5 More general types of character sums
168(2)
6.3 Some applications of character sums
170(15)
Alina Ostafe
Arne Winterhof
6.3.1 Applications of a simple character sum identity
170(1)
6.3.1.1 Hadamard matrices
170(1)
6.3.1.2 Cyclotomic complete mappings and check digit systems
171(1)
6.3.1.3 Periodic autocorrelation of cyclotomic generators
172(1)
6.3.2 Applications of Gauss and Jacobi sums
172(1)
6.3.2.1 Reciprocity laws
173(1)
6.3.2.2 Distribution of linear congruential pseudorandom numbers
174(1)
6.3.2.3 Diagonal equations, Waring's problem in finite fields, and covering radius of certain cyclic codes
175(1)
6.3.2.4 Hidden number problem and noisy interpolation
176(1)
6.3.3 Applications of the Weil bound
176(1)
6.3.3.1 Superelliptic and Artin-Schreier equations
177(1)
6.3.3.2 Stable quadratic polynomials
177(1)
6.3.3.3 Hamming distance of dual BCH codes
178(1)
6.3.4 Applications of Kloosterman sums
179(1)
6.3.4.1 Kloosterman equations and Kloosterman codes
179(1)
6.3.4.2 Distribution of inversive congruential pseudorandom numbers
180(1)
6.3.4.3 Nonlinearity of Boolean functions
180(1)
6.3.5 Incomplete character sums
181(1)
6.3.5.1 Finding deterministically linear factors of polynomials
181(1)
6.3.5.2 Measures of pseudorandomness
182(1)
6.3.6 Other character sums
183(1)
6.3.6.1 Distribution of primitive elements and powers
183(1)
6.3.6.2 Distribution of Diffie-Hellman triples
183(1)
6.3.6.3 Thin sets with small discrete Fourier transform
184(1)
6.3.6.4 Character sums over arbitrary sets
184(1)
6.4 Sum-product theorems and applications
185(8)
Moubariz Z. Garaev
6.4.1 Notation
185(1)
6.4.2 The sum-product estimate and its variants
186(2)
6.4.3 Applications
188(5)
7 Equations over finite fields
193(22)
7.1 General forms
193(8)
Daqing Wan
7.1.1 Affine hypersurfaces
193(2)
7.1.2 Projective hypersurfaces
195(1)
7.1.3 Toric hypersurfaces
196(1)
7.1.4 Artin-Schreier hypersurfaces
197(1)
7.1.5 Kummer hypersurfaces
198(1)
7.1.6 p-Adic estimates
199(2)
7.2 Quadratic forms
201(5)
Robert Fitzgerald
7.2.1 Basic definitions
201(1)
7.2.2 Quadratic forms over finite fields
202(2)
7.2.3 Trace forms
204(1)
7.2.4 Applications
205(1)
7.3 Diagonal equations
206(9)
Francis Castro
Ivelisse Rubio
7.3.1 Preliminaries
206(1)
7.3.2 Solutions of diagonal equations
207(3)
7.3.3 Generalizations of diagonal equations
210(1)
7.3.4 Waring's problem in finite fields
211(4)
8 Permutation polynomials
215(26)
8.1 One variable
215(15)
Gary L. Mullen
Qiang Wang
8.1.1 Introduction
215(1)
8.1.2 Criteria
216(1)
8.1.3 Enumeration and distribution of PPs
217(3)
8.1.4 Constructions of PPs
220(1)
8.1.5 PPs from permutations of multiplicative groups
221(3)
8.1.6 PPs from permutations of additive groups
224(1)
8.1.7 Other types of PPs from the AGW criterion
224(2)
8.1.8 Dickson and reversed Dickson PPs
226(2)
8.1.9 Miscellaneous PPs
228(2)
8.2 Several variables
230(2)
Rudolf Lidl
Gary L. Mullen
8.3 Value sets of polynomials
232(4)
Gary L. Mullen
Michael E. Zieve
8.3.1 Large value sets
233(1)
8.3.2 Small value sets
233(1)
8.3.3 General polynomials
234(1)
8.3.4 Lower bounds
234(1)
8.3.5 Examples
235(1)
8.3.6 Further value set papers
235(1)
8.4 Exceptional polynomials
236(5)
Michael E. Zieve
8.4.1 Fundamental properties
236(1)
8.4.2 Indecomposable exceptional polynomials
237(1)
8.4.3 Exceptional polynomials and permutation polynomials
238(1)
8.4.4 Miscellany
238(1)
8.4.5 Applications
239(2)
9 Special functions over finite fields
241(62)
9.1 Boolean functions
241(12)
Claude Carlet
9.1.1 Representation of Boolean functions
242(1)
9.1.1.1 Algebraic normal form
242(1)
9.1.1.2 Trace representation
243(1)
9.1.2 The Walsh transform
244(1)
9.1.3 Parameters of Boolean functions
244(2)
9.1.4 Equivalence of Boolean functions
246(1)
9.1.5 Boolean functions and cryptography
246(3)
9.1.6 Constructions of cryptographic Boolean functions
249(1)
9.1.6.1 Primary constructions of resilient functions
249(1)
9.1.6.2 Secondary constructions of resilient functions
249(1)
9.1.6.3 Constructions of highly nonlinear functions with optimal algebraic immunity
250(1)
9.1.7 Boolean functions and error correcting codes
251(1)
9.1.7.1 Reed-Muller codes
251(1)
9.1.7.2 Kerdock codes
251(1)
9.1.8 Boolean functions and sequences
251(1)
9.1.8.1 Boolean functions and cross correlation of m-sequences
252(1)
9.2 PN and APN functions
253(9)
Pascale Charpin
9.2.1 Functions from F2n into F2m
253(1)
9.2.2 Perfect Nonlinear (PN) functions
254(1)
9.2.3 Almost Perfect Nonlinear (APN) and Almost Bent (AB) functions
255(1)
9.2.4 APN permutations
256(1)
9.2.5 Properties of stability
257(1)
9.2.6 Coding theory point of view
258(1)
9.2.7 Quadratic APN functions
258(2)
9.2.8 APN monomials
260(2)
9.3 Bent and related functions
262(11)
Alexander Kholosha
Alexander Pott
9.3.1 Definitions and examples
262(2)
9.3.2 Basic properties of bent functions
264(1)
9.3.3 Bent functions and other combinatorial objects
265(1)
9.3.4 Fundamental classes of bent functions
266(2)
9.3.5 Boolean monomial and Niho bent functions
268(2)
9.3.6 p-ary bent functions in univariate form
270(1)
9.3.7 Constructions using planar and s-plateaued functions
271(1)
9.3.8 Vectorial bent functions and Kerdock codes
272(1)
9.4 κ-polynomials and related algebraic objects
273(5)
Robert Coulter
9.4.1 Definitions and preliminaries
273(2)
9.4.2 Pre-semifields, semifields, and isotopy
275(1)
9.4.3 Semifield constructions
275(1)
9.4.4 Semifields and nuclei
276(2)
9.5 Planar functions and commutative semifields
278(4)
Robert Coulter
9.5.1 Definitions and preliminaries
278(1)
9.5.2 Constructing affine planes using planar functions
279(1)
9.5.3 Examples, constructions, and equivalence
279(1)
9.5.4 Classification results, necessary conditions, and the Dembowski-Ostrom Conjecture
280(1)
9.5.5 Planar DO polynomials and commutative semifields of odd order
281(1)
9.6 Dickson polynomials Qiang Wang and Joseph L. Yucas
282(8)
9.6.1 Basics
282(2)
9.6.2 Factorization
284(1)
9.6.2.1 a-reciprocals of polynomials
285(1)
9.6.2.2 The maps φa and Ψa
286(1)
9.6.2.3 Factors of Dickson polynomials
286(1)
9.6.2.4 a-cyclotomic polynomials
287(1)
9.6.3 Dickson polynomials of the (κ + 1)-th kind
287(2)
9.6.4 Multivariate Dickson polynomials
289(1)
9.7 Schur's conjecture and exceptional covers
290(13)
Michael D. Fried
9.7.1 Rational function definitions
290(2)
9.7.2 MacCluer's Theorem and Schur's Conjecture
292(3)
9.7.3 Fiber product of covers
295(1)
9.7.4 Combining exceptional covers; the (Fq, Z) exceptional tower
296(2)
9.7.5 Exceptional rational functions; Serre's Open Image Theorem
298(2)
9.7.6 Davenport pairs and Poincare series
300(3)
10 Sequences over finite fields
303(42)
10.1 Finite field transforms
303(8)
Gary McGuire
10.1.1 Basic definitions and important examples
303(3)
10.1.2 Functions between two groups
306(1)
10.1.3 Discrete Fourier Transform
307(1)
10.1.4 Further topics
308(1)
10.1.4.1 Fourier spectrum
309(1)
10.1.4.2 Nonlinearity
309(1)
10.1.4.3 Characteristic functions
309(1)
10.1.4.4 Gauss sums
310(1)
10.1.4.5 Uncertainty principle
310(1)
10.2 LFSR sequences and maximal period sequences
311(6)
Harald Niederreiter
10.2.1 General properties of LFSR sequences
311(2)
10.2.2 Operations with LFSR sequences and characterizations
313(2)
10.2.3 Maximal period sequences
315(1)
10.2.4 Distribution properties of LFSR sequences
315(1)
10.2.5 Applications of LFSR sequences
316(1)
10.3 Correlation and autocorrelation of sequences
317(7)
Tor Helleseth
10.3.1 Basic definitions
317(1)
10.3.2 Autocorrelation of sequences
318(1)
10.3.3 Sequence families with low correlation
319(2)
10.3.4 Quaternary sequences
321(1)
10.3.5 Other correlation measures
322(2)
10.4 Linear complexity of sequences and multisequences
324(13)
Wilfried Meidl
Arne Winterhof
10.4.1 Linear complexity measures
324(3)
10.4.2 Analysis of the linear complexity
327(2)
10.4.3 Average behavior of the linear complexity
329(2)
10.4.4 Some sequences with large n-th linear complexity
331(1)
10.4.4.1 Explicit sequences
331(1)
10.4.4.2 Recursive nonlinear sequences
332(1)
10.4.4.3 Legendre sequence and related bit sequences
333(1)
10.4.4.4 Elliptic curve sequences
334(1)
10.4.5 Related measures
334(1)
10.4.5.1 Kolmogorov complexity
334(1)
10.4.5.2 Lattice test
335(1)
10.4.5.3 Correlation measure of order κ
335(1)
10.4.5.4 FCSR and p-adic span
335(1)
10.4.5.5 Discrepancy
336(1)
10.5 Algebraic dynamical systems over finite fields
337(8)
Igor Shparlinski
10.5.1 Introduction
337(1)
10.5.2 Background and main definitions
337(1)
10.5.3 Degree growth
338(2)
10.5.4 Linear independence and other algebraic properties of iterates
340(1)
10.5.5 Multiplicative independence of iterates
341(1)
10.5.6 Trajectory length
341(1)
10.5.7 Irreducibility of iterates
342(1)
10.5.8 Diameter of partial trajectories
343(2)
11 Algorithms
345(60)
11.1 Computational techniques
345(19)
Christophe Doche
11.1.1 Preliminaries
346(1)
11.1.1.1 Prime field generation
346(1)
11.1.1.2 Extension field generation
347(2)
11.1.1.3 Primitive elements
349(1)
11.1.1.4 Order of an irreducible polynomial and primitive polynomials
349(1)
11.1.1.5 Minimal polynomial of an element
350(1)
11.1.2 Representation of finite fields
350(1)
11.1.3 Modular reduction
351(1)
11.1.3.1 Prime fields
351(2)
11.1.3.2 Extension fields
353(1)
11.1.4 Addition
354(1)
11.1.5 Multiplication
354(1)
11.1.5.1 Prime fields
354(1)
11.1.5.2 Extension fields
355(1)
11.1.6 Squaring
356(1)
11.1.6.1 Finite fields of odd characteristic
356(1)
11.1.6.2 Finite fields of characteristic two
356(1)
11.1.7 Exponentiation
356(1)
11.1.7.1 Prime fields
356(1)
11.1.7.2 Extension fields
357(1)
11.1.8 Inversion
358(1)
11.1.8.1 Prime fields
359(1)
11.1.8.2 Extension fields
360(1)
11.1.9 Squares and square roots
360(1)
11.1.9.1 Finite fields of odd characteristic
361(2)
11.1.9.2 Finite fields of even characteristic
363(1)
11.2 Univariate polynomial counting and algorithms
364(10)
Daniel Panario
11.2.1 Classical counting results
364(1)
11.2.2 Analytic combinatorics approach
365(2)
11.2.3 Some illustrations of polynomial counting
367(1)
11.2.3.1 Number of irreducible factors of a polynomial
367(1)
11.2.3.2 Factorization patterns
368(1)
11.2.3.3 Largest and smallest degree irreducibles
369(2)
11.2.3.4 Greatest common divisor of polynomials
371(1)
11.2.3.5 Relations to permutations and integers
372(2)
11.3 Algorithms for irreducibility testing and for constructing irreducible polynomials
374(6)
Marie Giesbrecht
11.3.1 Introduction
374(1)
11.3.2 Early irreducibility tests of univariate polynomials
375(1)
11.3.3 Rabin's irreducibility test
376(1)
11.3.4 Constructing irreducible polynomials: randomized algorithms
377(1)
11.3.5 Ben-Or's algorithm for construction of irreducible polynomials
377(1)
11.3.6 Shoup's algorithm for construction of irreducible polynomials
378(1)
11.3.7 Constructing irreducible polynomials: deterministic algorithms
378(1)
11.3.8 Construction of irreducible polynomials of approximate degree
379(1)
11.4 Factorization of univariate polynomials
380(2)
Joachim von zur Gathen
11.5 Factorization of multivariate polynomials
382(11)
Erich Kaltofen
Gregoire Lecerf
11.5.1 Factoring dense multivariate polynomials
382(1)
11.5.1.1 Separable factorization
382(2)
11.5.1.2 Squarefree factorization
384(1)
11.5.1.3 Bivariate irreducible factorization
384(2)
11.5.1.4 Reduction from any number to two variables
386(1)
11.5.2 Factoring sparse multivariate polynomials
387(1)
11.5.2.1 Ostrowski's theorem
388(1)
11.5.2.2 Irreducibility tests based on indecomposability of polytopes
388(1)
11.5.2.3 Sparse bivariate Hensel lifting driven by polytopes
388(1)
11.5.2.4 Convex-dense bivariate factorization
389(1)
11.5.3 Factoring straight-line programs and black boxes
390(3)
11.6 Discrete logarithms over finite fields
393(8)
Andrew Odlyzko
11.6.1 Basic definitions
393(1)
11.6.2 Modern computer implementations
394(1)
11.6.3 Historical remarks
394(1)
11.6.4 Basic properties of discrete logarithms
395(1)
11.6.5 Chinese Remainder Theorem reduction: The Silver-Pohlig-Hellman algorithm
395(1)
11.6.6 Baby steps-giant steps algorithm
396(1)
11.6.7 Pollard rho and kangaroo methods for discrete logarithms
397(1)
11.6.8 Index calculus algorithms for discrete logarithms in finite fields
397(2)
11.6.9 Smooth integers and smooth polynomials
399(1)
11.6.10 Sparse linear systems of equations
399(1)
11.6.11 Current discrete logarithm records
400(1)
11.7 Standard models for finite fields Bart de Smit and Hendrik Lenstra
401(4)
12 Curves over finite fields
405(88)
12.1 Introduction to function fields and curves
406(16)
Arnaldo Garcia
Henning Stichtenoth
12.1.1 Valuations and places
406(3)
12.1.2 Divisors and Riemann-Roch theorem
409(4)
12.1.3 Extensions of function fields
413(6)
12.1.4 Differentials
419(2)
12.1.5 Function fields and curves
421(1)
12.2 Elliptic curves
422(18)
Joseph Silverman
12.2.1 Weierstrass equations
423(2)
12.2.2 The group law
425(2)
12.2.3 Isogenics and endomorphisms
427(3)
12.2.4 The number of points in E(q)
430(1)
12.2.5 Twists
431(1)
12.2.6 The torsion subgroup and the Tate module
432(1)
12.2.7 The Weil pairing and the Tate pairing
433(2)
12.2.8 The endomorphism ring and automorphism group
435(1)
12.2.9 Ordinary and supersingular elliptic curves
436(2)
12.2.10 The zeta function of an elliptic curve
438(1)
12.2.11 The elliptic curve discrete logarithm problem
439(1)
12.3 Addition formulas for elliptic curves
440(7)
Daniel J. Bernstein
Tanja Lange
12.3.1 Curve shapes
440(1)
12.3.2 Addition
441(1)
12.3.3 Coordinate systems
442(1)
12.3.4 Explicit formulas
443(1)
12.3.5 Short Weierstrass curves, large characteristic: y2 = x3 - 3x + b
444(1)
12.3.6 Short Weierstrass curves, characteristic 2, ordinary case: y2 + xy = x3 + a2x2 +a6
444(1)
12.3.7 Montgomery curves: by2 = x3 + ax2 +x
445(1)
12.3.8 Twisted Edwards curves: ax2 + y2 = 1 + dx2y2
446(1)
12.4 Hyperelliptic curves
447(9)
Michael John Jacobson, Jr.
Renate Scheidler
12.4.1 Hyperelliptic equations
447(2)
12.4.2 The degree zero divisor class group
449(1)
12.4.3 Divisor class arithmetic over finite fields
450(3)
12.4.4 Endomorphisms and supersingularity
453(1)
12.4.5 Class number computation
453(1)
12.4.6 The Tate-Lichtenbaum pairing
454(1)
12.4.7 The hyperelliptic curve discrete logarithm problem
455(1)
12.5 Rational points on curves
456(8)
Arnaldo Garcia
Henning Stichtenoth
12.5.1 Rational places
457(1)
12.5.2 The Zeta function of a function field
458(1)
12.5.3 Bounds for the number of rational places
459(2)
12.5.4 Maximal function fields
461(1)
12.5.5 Asymptotic bounds
462(2)
12.6 Towers
464(5)
Arnaldo Garcia
Henning Stichtenoth
12.6.1 Introduction to towers
464(2)
12.6.2 Examples of towers
466(3)
12.7 Zeta functions and L-functions
469(10)
Lei Fu
12.7.1 Zeta functions
469(5)
12.7.2 L-functions
474(3)
12.7.3 The case of curves
477(2)
12.8 p-adic estimates of zeta functions and L-functions
479(9)
Regis Blache
12.8.1 Introduction
479(1)
12.8.2 Lower bounds for the first slope
480(1)
12.8.3 Uniform lower bounds for Newton polygons
481(2)
12.8.4 Variation of Newton polygons in a family
483(2)
12.8.5 The case of curves and abelian varieties
485(3)
12.9 Computing the number of rational points and zeta functions
488(5)
Daqing Wan
12.9.1 Point counting: sparse input
488(1)
12.9.2 Point counting: dense input
489(1)
12.9.3 Computing zeta functions: general case
490(1)
12.9.4 Computing zeta functions: curve case
491(2)
13 Miscellaneous theoretical topics
493(56)
13.1 Relations between integers and polynomials over finite fields
493(7)
Gove Effinger
13.1.1 The density of primes and irreducibles
494(1)
13.1.2 Primes and irreducibles in arithmetic progression
495(1)
13.1.3 Twin primes and irreducibles
495(1)
13.1.4 The generalized Riemann hypothesis
496(1)
13.1.5 The Goldbach problem over finite fields
497(1)
13.1.6 The Waring problem over finite fields
498(2)
13.2 Matrices over finite fields
500(10)
Dieter Jungnickel
13.2.1 Matrices of specified rank
500(1)
13.2.2 Matrices of specified order
501(2)
13.2.3 Matrix representations of finite fields
503(1)
13.2.4 Circulant and orthogonal matrices
504(2)
13.2.5 Symmetric and skew-symmetric matrices
506(1)
13.2.6 Hankel and Toeplitz matrices
507(2)
13.2.7 Determinants
509(1)
13.3 Classical groups over finite fields
510(10)
Zhe-Xian Wan
13.3.1 Linear groups over finite fields
510(2)
13.3.2 Symplectic groups over finite fields
512(2)
13.3.3 Unitary groups over finite fields
514(2)
13.3.4 Orthogonal groups over finite fields of characteristic not two
516(3)
13.3.5 Orthogonal groups over finite fields of characteristic two
519(1)
13.4 Computational linear algebra over finite fields
520(15)
Jean-Guillaume Dumas
Clement Pernet
13.4.1 Dense matrix multiplication
521(1)
13.4.1.1 Tiny finite fields
521(2)
13.4.1.2 Word size prime fields
523(1)
13.4.1.3 Large finite fields
524(1)
13.4.1.4 Large matrices: subcubic time complexity
524(1)
13.4.2 Dense Gaussian elimination and echelon forms
525(1)
13.4.2.1 Building blocks
525(1)
13.4.2.2 PLE decomposition
526(1)
13.4.2.3 Echelon forms
527(1)
13.4.3 Minimal and characteristic polynomial of a dense matrix
528(2)
13.4.4 Blackbox iterative methods
530(1)
13.4.4.1 Minimal polynomial and the Wiedemann algorithm
530(1)
13.4.4.2 Rank, determinant, and characteristic polynomial
531(1)
13.4.4.3 System solving and the Lanczos algorithm
531(1)
13.4.5 Sparse and structured methods
532(1)
13.4.5.1 Reordering
532(1)
13.4.5.2 Structured matrices and displacement rank
532(2)
13.4.6 Hybrid methods
534(1)
13.4.6.1 Hybrid sparse-dense methods
534(1)
13.4.6.2 Block-iterative methods
534(1)
13.5 Carlitz and Drinfeld modules
535(14)
David Goss
13.5.1 Quick review
536(1)
13.5.2 Drinfeld modules: definition and analytic theory
537(2)
13.5.3 Drinfeld modules over finite fields
539(1)
13.5.4 The reduction theory of Drinfeld modules
539(1)
13.5.5 The A-module of rational points
540(1)
13.5.6 The invariants of a Drinfeld module
540(1)
13.5.7 The L-series of a Drinfeld module
541(1)
13.5.8 Special values
542(1)
13.5.9 Measures and symmetries
542(2)
13.5.10 Multizeta
544(1)
13.5.11 Modular theory
544(1)
13.5.12 Transcendency results
545(4)
Part III Applications
14 Combinatorial
549(110)
14.1 Latin squares
550(6)
Gary L. Mullen
14.1.1 Prime powers
551(1)
14.1.2 Non-prime powers
552(1)
14.1.3 Frequency squares
553(1)
14.1.4 Hypercubes
553(1)
14.1.5 Connections to affine and projective planes
554(1)
14.1.6 Other finite field constructions for MOLS
555(1)
14.2 Lacunary polynomials over finite fields
556(7)
Simeon Ball
Aart Blokhuis
14.2.1 Introduction
556(1)
14.2.2 Lacunary polynomials
556(1)
14.2.3 Directions and Redei polynomials
557(1)
14.2.4 Sets of points determining few directions
558(1)
14.2.5 Lacunary polynomials and blocking sets
559(2)
14.2.6 Lacunary polynomials and blocking sets in planes of prime order
561(1)
14.2.7 Lacunary polynomials and multiple blocking sets
562(1)
14.3 Affine and projective planes
563(11)
Gary Ebert
Leo Storme
14.3.1 Projective planes
563(1)
14.3.2 Affine planes
564(1)
14.3.3 Translation planes and spreads
565(2)
14.3.4 Nest planes
567(1)
14.3.5 Flag-transitive affine planes
568(1)
14.3.6 Subplanes
569(2)
14.3.7 Embedded unitals
571(1)
14.3.8 Maximal arcs
572(1)
14.3.9 Other results
573(1)
14.4 Projective spaces
574(15)
James W.P. Hirschfeld
Joseph A. Thas
14.4.1 Projective and affine spaces
574(2)
14.4.2 Collineations, correlations, and coordinate frames
576(2)
14.4.3 Polarities
578(4)
14.4.4 Partitions and cyclic projectivities
582(1)
14.4.5 κ-Arcs
583(3)
14.4.6 κ-Arcs and linear MDS codes
586(1)
14.4.7 κ-Caps
587(2)
14.5 Block designs
589(10)
Charles J. Colbourn
Jeffrey H. Dinitz
14.5.1 Basics
589(1)
14.5.2 Triple systems
590(2)
14.5.3 Difference families and balanced incomplete block designs
592(2)
14.5.4 Nested designs
594(2)
14.5.5 Pairwise balanced designs
596(1)
14.5.6 Group divisible designs
596(1)
14.5.7 t-designs
597(1)
14.5.8 Packing and covering
598(1)
14.6 Difference sets Alexander Pott
599(8)
14.6.1 Basics
599(2)
14.6.2 Difference sets in cyclic groups
601(2)
14.6.3 Difference sets in the additive groups of finite fields
603(1)
14.6.4 Difference sets and Hadamard matrices
604(1)
14.6.5 Further families of difference sets
605(1)
14.6.6 Difference sets and character sums
606(1)
14.6.7 Multipliers
606(1)
14.7 Other combinatorial structures
607(2)
Jeffrey H. Dinitz
Charles J. Colbourn
14.7.1 Association schemes
607(1)
14.7.2 Costas arrays
608(1)
147.3 Conference matrices
609(10)
14.7.4 Covering arrays
610(1)
14.7.5 Hall triple systems
611(1)
14.7.6 Ordered designs and perpendicular arrays
611(1)
14.7.7 Perfect hash families
612(2)
14.7.8 Room squares and starters
614(3)
14.7.9 Strongly regular graphs
617(1)
14.7.10 Whist tournaments
617(2)
14.8 (t, m, s)-nets and (t, s)-sequences
619(11)
Harald Niederreiter
14.8.1 (t, m, s)-nets
619(2)
14.8.2 Digital (t, m, s)-nets
621(2)
14.8.3 Constructions of (t, m, s)-nets
623(2)
14.8.4 (t, s)-sequences and (T, s)-sequences
625(1)
14.8.5 Digital (t, s)-sequences and digital (T, s)-sequences
626(2)
14.8.6 Constructions of (t, s)-sequences and (T, s)-sequences
628(2)
14.9 Applications and weights of multiples of primitive and other polynomials
630(12)
Brett Stevens
14.9.1 Applications where weights of multiples of a base polynomial are relevant
630(1)
14.9.1.1 Applications from other Handbook sections
630(1)
14.9.1.2 Application of polynomials to the construction of orthogonal arrays
631(1)
14.9.1.3 Application of polynomials to a card trick
632(1)
14.9.2 Weights of multiples of polynomials
633(1)
14.9.2.1 General bounds on d ((Cfn))
633(2)
14.9.2.2 Bounds on d ((Cfn)) for polynomials of specific degree
635(3)
14.9.2.3 Bounds on d ((Cfn)) for polynomials of specific weight
638(4)
14.10 Ramanujan and expander graphs
642(17)
M. Ram Murty
Sebastian M. Cioaba
14.10.1 Graphs, adjacency matrices, and eigenvalues
643(3)
14.10.2 Ramanujan graphs
646(2)
14.10.3 Expander graphs
648(1)
14.10.4 Cayley graphs
649(3)
14.10.5 Explicit constructions of Ramanujan graphs
652(3)
14.10.6 Combinatorial constructions of expanders
655(2)
14.10.7 Zeta functions of graphs
657(2)
15 Algebraic coding theory
659(82)
15.1 Basic coding properties and bounds
659(44)
Ian Blake
W. Cary Huffman
15.1.1 Channel models and error correction
659(2)
15.1.2 Linear codes
661(4)
15.1.2.1 Standard array decoding of linear codes
665(1)
15.1.2.2 Hamming codes
666(1)
15.1.2.3 Reed-Muller codes
667(1)
15.1.2.4 Subfield and trace codes
668(1)
15.1.2.5 Modifying linear codes
669(1)
15.1.2.6 Bounds on codes
670(3)
15.1.2.7 Asymptotic bounds
673(1)
15.1.3 Cyclic codes
674(1)
15.1.3.1 Algebraic prerequisites
675(1)
15.1.3.2 Properties of cyclic codes
676(1)
15.1.3.3 Classes of cyclic codes
677(12)
15.1.4 A spectral approach to coding
689(1)
15.1.5 Codes and combinatorics
690(2)
15.1.6 Decoding
692(1)
15.1.6.1 Decoding BCH codes
692(1)
15.1.6.2 The Peterson-Gorenstein-Zierler decoder
692(1)
15.1.6.3 Berlekamp-Massey decoding
693(1)
15.1.6.4 Extended Euclidean algorithm decoding
694(1)
15.1.6.5 Welch-Berlekamp decoding of GRS codes
695(1)
15.1.6.6 Majority logic decoding
696(1)
15.1.6.7 Generalized minimum distance decoding
696(2)
15.1.6.8 List decoding - decoding beyond the minimum distance bound
698(1)
15.1.7 Codes over 4
699(3)
15.1.8 Conclusion
702(1)
15.2 Algebraic-geometry codes
703(10)
Harald Niederreiter
15.2.1 Classical algebraic-geometry codes
703(2)
15.2.2 Generalized algebraic-geometry codes
705(3)
15.2.3 Function-field codes
708(2)
15.2.4 Asymptotic bounds
710(3)
15.3 LDPC and Gallager codes over finite fields
713(6)
Ian Blake
W. Cary Huffman
15.4 Turbo codes over finite fields
719(8)
Oscar Takeshita
15.4.1 Introduction
719(1)
15.4.1.1 Historical background
719(1)
15.4.1.2 Terminology
719(2)
15.4.2 Convolutional codes
721(1)
15.4.2.1 Non-recursive convolutional codes
721(1)
15.4.2.2 Distance properties of non-recursive convolutional codes
722(1)
15.4.2.3 Recursive convolutional codes
723(1)
15.4.2.4 Distance properties of recursive convolutional codes
723(1)
15.4.3 Permutations and interleavers
724(1)
15.4.4 Encoding and decoding
725(1)
15.4.5 Design of turbo codes
725(1)
15.4.5.1 Design of the recursive convolutional code
726(1)
15.4.5.2 Design of interleavers
726(1)
15.5 Raptor codes
727(8)
Ian Blake
W. Cary Huffman
15.5.1 Tornado codes
728(2)
15.5.2 LT and fountain codes
730(3)
15.5.3 Raptor codes
733(2)
15.6 Polar codes
735(6)
Simon Litsyn
15.6.1 Space decomposition
735(1)
15.6.2 Vector transformation
736(1)
15.6.3 Decoding
737(2)
15.6.4 Historical notes and other results
739(2)
16 Cryptography
741(84)
16.1 Introduction to cryptography
741(9)
Alfred Menezes
16.1.1 Goals of cryptography
742(1)
16.1.2 Symmetric-key cryptography
742(1)
16.1.2.1 Stream ciphers
742(1)
16.1.2.2 Block ciphers
743(1)
16.1.3 Public-key cryptography
744(1)
16.1.3.1 RSA
744(2)
16.1.3.2 Discrete logarithm cryptosystems
746(1)
16.1.3.3 DSA
746(1)
16.1.4 Pairing-based cryptography
747(2)
16.1.5 Post-quantum cryptography
749(1)
16.2 Stream and block ciphers
750(14)
Guang Gong
Kishan Chand Gupta
16.2.1 Basic concepts of stream ciphers
751(2)
16.2.2 (Alleged) RC4 algorithm
753(1)
16.2.3 WG stream cipher
754(4)
16.2.4 Basic structures of block ciphers
758(1)
16.2.5 RC6
759(1)
16.2.6 Advanced Encryption Standard (AES) RIJNDAEL
760(4)
16.3 Multivariate cryptographic systems
764(20)
Jintai Ding
16.3.1 The basics of multivariate PKCs
765(1)
16.3.1.1 The standard (bipolar) construction of MPKCs
765(1)
16.3.1.2 Implicit form MPKCs
766(1)
16.3.1.3 Isomorphism of polynomials
767(1)
16.3.2 Main constructions and variations
767(1)
16.3.2.1 Historical constructions
767(1)
16.3.2.2 Triangular constructions
768(1)
16.3.2.3 Big-field families: Matsumoto-Imai (C*) and HFE
769(1)
16.3.2.4 Oil and vinegar (unbalanced and balanced) and variations
770(2)
16.3.2.5 UOV as a booster stage
772(1)
16.3.2.6 Plus-Minus variations
772(1)
16.3.2.7 Internal perturbation
773(1)
16.3.2.8 Vinegar as an external perturbation and projection
774(1)
16.3.2.9 TTM and related schemes: "lock" or repeated triangular
774(1)
16.3.2.10 Intermediate fields: MFE and IC
775(1)
16.3.2.11 Odd characteristic
776(1)
16.3.2.12 Other constructions
776(1)
16.3.3 Standard attacks
776(1)
16.3.3.1 Linearization equations
776(1)
16.3.3.2 Critical bilinear relations
776(1)
16.3.3.3 HOLEs (higher-order linearization equations)
777(1)
16.3.3.4 Differential attacks
777(1)
16.3.3.5 Attacking internal perturbations
777(1)
16.3.3.6 The skew symmetric transformation
778(1)
16.3.3.7 Multiplicative symmetry
779(1)
16.3.3.8 Rank attacks
779(1)
16.3.3.9 MinRank attacks on big-field schemes
780(1)
16.3.3.10 Distilling oil from vinegar and other attacks on UOV
780(1)
16.3.3.11 Reconciliation
781(1)
16.3.3.12 Direct attacks using polynomial solvers
781(1)
16.3.4 The future
782(2)
16.4 Elliptic curve cryptographic systems
784(13)
Andreas Enge
16.4.1 Cryptosystems based on elliptic curve discrete logarithms
784(1)
16.4.1.1 Key sizes
784(1)
16.4.1.2 Cryptographic primitives
784(1)
16.4.1.3 Special curves
785(2)
16.4.1.4 Random curves: point counting
787(1)
16.4.2 Pairing based cryptosystems
788(1)
16.4.2.1 Cryptographic pairings
789(2)
16.4.2.2 Pairings and twists
791(1)
16.4.2.3 Explicit isomorphisms
792(1)
16.4.2.4 Curve constructions
793(2)
16.4.2.5 Hashing into elliptic curves
795(2)
16.5 Hyperelliptic curve cryptographic systems
797(6)
Nicolas Theriault
16.5.1 Cryptosystems based on hyperelliptic curve discrete logarithms
797(1)
16.5.2 Curves of genus 2
797(1)
16.5.3 Curves of genus 3
798(1)
16.5.4 Curves of higher genus
799(1)
16.5.5 Key sizes
799(2)
16.5.6 Special curves
801(1)
16.5.7 Random curves: point counting
802(1)
16.5.8 Pairings in hyperelliptic curves
803(1)
16.6 Cryptosystems arising from Abelian varieties
803(8)
Kumar Murty
16.6.1 Definitions
804(1)
16.6.2 Examples
804(1)
16.6.3 Jacobians of curves
804(1)
16.6.4 Restriction of scalars
804(1)
16.6.5 Endomorphisms
805(1)
16.6.6 The characteristic polynomial of an endomorphism
805(1)
16.6.7 Zeta functions
805(2)
16.6.8 Arithmetic on an Abelian variety
807(1)
16.6.9 The group order
808(1)
16.6.10 The discrete logarithm problem
808(1)
16.6.11 Weil descent attack
809(1)
16.6.12 Pairings based cryptosystems
810(1)
16.7 Binary extension field arithmetic for hardware implementations
811(14)
M. Anwarul Hasan
Haining Fan
16.7.1 Preamble and basic terminologies
811(1)
16.7.2 Arithmetic using polynomial operations
812(4)
16.7.3 Arithmetic using matrix operations
816(1)
16.7.4 Arithmetic using normal bases
817(2)
16.7.5 Multiplication using optimal normal bases
819(3)
16.7.6 Additional notes
822(3)
17 Miscellaneous applications
825(26)
17.1 Finite fields in biology
825(9)
Franziska Hinkelmann
Reinhard Laubenbacher
17.1.1 Polynomial dynamical systems as framework for discrete models in systems biology
825(1)
17.1.2 Polynomial dynamical systems
826(1)
17.1.3 Discrete model types and their translation into PDS
827(2)
17.1.3.1 Boolean network models
829(1)
17.1.3.2 Logical models
829(2)
17.1.3.3 Petri nets and agent-based models
831(1)
17.1.4 Reverse engineering and parameter estimation
831(1)
17.1.4.1 The minimal-sets algorithm
831(1)
17.1.4.2 Parameter estimation using the Grobner fan of an ideal
831(1)
17.1.5 Software for biologists and computer algebra software
832(1)
17.1.6 Specific polynomial dynamical systems
832(1)
17.1.6.1 Nested canalyzing functions
832(2)
17.1.6.2 Parameter estimation resulting in nested canalyzing functions
834(1)
17.1.6.3 Linear polynomial dynamical systems
834(1)
17.1.6.4 Conjunctive/disjunctive networks
834(1)
17.2 Finite fields in quantum information theory
834(7)
Martin Roetteler
Arne Winterhof
17.2.1 Mutually unbiased bases
835(1)
17.2.2 Positive operator-valued measures
836(1)
17.2.3 Quantum error-correcting codes
837(2)
17.2.4 Period finding
839(1)
17.2.5 Quantum function reconstruction
840(1)
17.2.6 Further connections
840(1)
17.3 Finite fields in engineering
841(10)
Jonathan Jedwab
Kai-Uwe Schmidt
17.3.1 Binary sequences with small aperiodic autocorrelation
841(1)
17.3.2 Sequence sets with small aperiodic auto- and crosscorrelation
842(1)
17.3.3 Binary Golay sequence pairs
843(1)
17.3.4 Optical orthogonal codes
844(1)
17.3.5 Sequences with small Hamming correlation
845(1)
17.3.6 Rank distance codes
846(1)
17.3.7 Space-time coding
847(1)
17.3.8 Coding over networks
848(3)
Bibliography 851(160)
Index 1011
Gary L. Mullen is a professor of mathematics at The Pennsylvania State University.

Daniel Panario is a professor of mathematics at Carleton University.