Finite Fields: Theory and Computation: The Meeting Point of Number Theory, Computer Science, Coding Theory and Cryptography

Front Cover
Springer Science & Business Media, May 31, 1999 - Mathematics - 528 pages
This book is mainly devoted to some computational and algorithmic problems in finite fields such as, for example, polynomial factorization, finding irreducible and primitive polynomials, the distribution of these primitive polynomials and of primitive points on elliptic curves, constructing bases of various types and new applications of finite fields to other areas of mathematics. For completeness we in clude two special chapters on some recent advances and applications of the theory of congruences (optimal coefficients, congruential pseudo-random number gener ators, modular arithmetic, etc.) and computational number theory (primality testing, factoring integers, computation in algebraic number theory, etc.). The problems considered here have many applications in Computer Science, Cod ing Theory, Cryptography, Numerical Methods, and so on. There are a few books devoted to more general questions, but the results contained in this book have not till now been collected under one cover. In the present work the author has attempted to point out new links among different areas of the theory of finite fields. It contains many very important results which previously could be found only in widely scattered and hardly available conference proceedings and journals. In particular, we extensively review results which originally appeared only in Russian, and are not well known to mathematicians outside the former USSR.
 

Contents

INTRODUCTION
1
LINKS FLOWCHART
13
POLYNOMIAL FACTORIZATION
17
12 Counting the Number of Points on Curves and Varieties and Multivariate Factorization
34
13 Other Polynomial Decompositions
42
FINDING IRREDUCIBLE AND PRIMITIVE POLYNOMIALS
45
22 Construction of Primitive Polynomials and Generating Sets
52
THE DISTRIBUTION OF IRREDUCIBLE PRIMITIVE AND OTHER SPECIAL POLYNOMIALS AND MATRICES
65
72 Applications of Recurrence Sequences
245
73 BCH and Other Cyclic Linear Codes and Recurrence Sequences
255
FINITE FIELDS AND DISCRETE MATHEMATICS
265
82 Permutation Polynomials and Other Polynomial Mappings
282
83 Graph Theory Boolean Functions Combinatorics and Integration Nets
297
84 Enumeration Problems in Finite Fields
319
CONGRUENCES
325
92 Residues of Exponential Functions
329

32 Irreducible and Primitive Polynomials of Small Height and Weight
86
33 Sparse Polynomials
91
34 Applications to Algebraic Number Fields
97
BASES AND COMPUTATION IN FINITE FIELDS
99
42 Discrete Logarithm and Zechs Logarithm
112
43 Polynomial Multiplication and Multiplicative Complexity in Finite Fields
117
44 Linear Algebra Polynomial Interpolation and Other Algorithms in Finite Fields
127
CODING THEORY AND ALGEBRAIC CURVES
149
52 Codes and Exponential Sums
185
53 Codes and Lattice Packings and Coverings
205
ELLIPTIC CURVES
215
62 Finding the Group Structure of Elliptic Curves
231
RECURRENCE SEQUENCES IN FINITE FIELDS AND CYCLIC LINEAR CODES
239
93 Modular Arithmetic
345
94 Other Applications
349
SOME RELATED PROBLEMS
361
102 Computational Algebraic Number Theory
372
103 Algebraic Complexity Theory
376
104 Polynomials with Integer Coefficients
387
APPENDIX 1
403
APPENDIX 2
405
APPENDIX 3
407
REFERENCES
409
INDEX
525
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information