Finite Fields: Theory and Computation: The Meeting Point of Number Theory, Computer Science, Coding Theory and CryptographyThis 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 |
Other editions - View all
Finite Fields: Theory and Computation: The Meeting Point of Number Theory ... Igor Shparlinski No preview available - 2010 |
Common terms and phrases
Acta Arithm algebraic number fields Amer Appl applications arithmetic operations asymptotic Berlin character sums coding theory coefficients computing congruences conjecture considered construction cryptography cryptosystem cyclic define denote deterministic Discr discrete logarithm distribution elliptic curves equations estimate exponential sums factorization algorithm field F finite fields formula Fq[x function fields given graphs hyper-elliptic curves IEEE Trans integer integer factorization irreducible polynomials lattice Lect linear complexity linear recurrence sequences log log lower bound Matem Math matrix Mn(q modulo multiplicative multivariate polynomials nontrivial normal bases Notes in Comp number of solutions Number Theory obtained paper permutation polynomials polynomial factorization polynomial ƒ polynomial of degree polynomials over finite Preprint prime numbers primitive polynomials primitive root problem Proc proof pseudo-random number quadratic random recurrence sequences residue Russian Section shown sparse polynomials Springer-Verlag Symb Symp Theorem Univ upper bound values vector
References to this book
Proceedings of the First International Workshop on Coding and Cryptology ... Yongqing Li No preview available - 2008 |