Coding Theory
– Finite fields and their equations and characters: codes, sequences and nonlinear functions

Finite fields have a wide variety of applications in modern information technology. Especially, they are applied in coding theory, sequence design and cryptography.

In coding theory, finite fields are used in construction of codes and then the study of their properties and design of decoding algorithms naturally leads to equations and characters of finite fields. For instance, weight distribution of a cyclic code can be calculated by means of character sums which in turn lead to equations over finite fields.

In sequence design, one wants to find large families of sequences with good correlation properties. Such sequences are then used as signature sequences, in synchronizing of signals and position location, for example. Linear recurring sequences over finite fields are easily generated using shift registers and therefore are good candidates for technical applications. When 0 and 1 in these sequences are interpreted as elements from the finite field Z₂, then the periodic correlation function of a linear recurring sequence can represented as a character sum in an extension field of Z₂ and its values be calculated or estimated at least.

Finite fields come in handy in cryptography too. For instance, in block ciphers such as DES, the round functions (S-boxes) need to possess non-linearity. Nonlinearity in turn can be measured by means of equations and characters over finite fields. Nonlinear functions such as APN functions, maximally nonlinear functions and bent functions have received much attention lately, and all three classes are best studied with the aid of finite field characters.

Finite fields (and their characters as well) are also an essential tool in many areas of combinatorial theory, e.g. design theory and finite geometry.

References:

1. Rudolf Lidl and Harald Niederreiter: Finite fields, Encyclopedia of Mathematics and its Applications, 20. Addison-Wesley Publishing Company, Reading, MA, 1983.
2. Tor Helleseth and P. Vijay Kumar: Sequences with low correlation. Handbook of coding theory, Vol. II, 1765-1853, North-Holland, Amsterdam, 1998.
3. Tor Helleseth, Jyrki Lahtonen and Petri Rosendahl: On Niho type cross-correlation functions of m-sequences. Finite Fields Appl. 13(2):305-317, 2007.
4. Iiro Honkala and Aimo Tietäväinen: Codes and number theory. Handbook of coding theory, Vol. II, 1141-1194, North-Holland, Amsterdam, 1998.
5. Kalle Ranto and Petri Rosendahl: On four-valued Niho-type cross-correlation functions of m-sequences. IEEE Trans. Inform. Theory 52(12):5533-5536, 2006.
6. Petri Rosendahl: Niho Type Cross-Correlation Functions and Related Equations. PhD Thesis, Turku 2004.
7. Petri Rosendahl: On Cusick's method and value sets of certain polynomials over finite fields. SIAM J. Discrete Math. 23(1): 333-343, 2008/09.