# Theory and Applications of Finite Fields

All abstracts
Size: 182 kb
Organizers:
• Daniel Panario (Carleton University)
• Luciane Quoos (Federal University of Rio de Janeiro)
• Ivelisse Rubio (University of Puerto Rico)
• David Thomson (Carleton University)
• Toni Bluher
Department of Defense (United States)
Dickson polynomials
PDF abstract
Size: 75 kb
Dickson polynomials, which are close relatives of the Chebyshev polynomials, are defined by the recursion $D_0(x) = 2$, $D_1(x) = x$, and $D_{k+1}(x) = x D_k(x) - D_{k-1}(x)$. The American mathematician Leonard Eugene Dickson proved in his PhD thesis (1896) that $D_k(x)$ is a permutation polynomial on the field with $p^n$ elements if and only if GCD$(k,p^{2n}-1) = 1$. Since then, there have been many theorems about the values taken by Dickson polynomials over finite fields. We obtain new results following this theme, including some surprising connections with elementary number theory. This talk assumes only a background in finite fields.
• Antonio Cafure
Universidad de Buenos Aires, (UBA- Buenos Aires, Argentina)
Cyclotomic polinomials over finite fields
PDF abstract
Size: 76 kb
Let $n$ be an odd natural number and let $p$ be an odd prime such that $p \nmid n$. Following the techniques of [1] and well known results about cyclotomic polynomials, we are able to show that the coefficients of the cyclotomic polynomial $\Phi_{np} \in \mathbb Q[t]$ can be computed as the unique solution of a linear system of equations $T x = b$, where $T$ is a semicirculant matrix involving coefficientes of $\Phi_n$, and $b$ is a vector whose entries are certain coefficients of $\Phi_n$ determined according to some congruences modulo $p$. In this talk we will study to what extent this characterization of cyclotomic polynomials over the rationals may be considered over a finite field and the potential implications of such a characterization. \bigskip [1] \textsc{A. Cafure y E. Cesaratto}. Irreducibility criteria for reciprocal polynomials and applications. Am. Math. Month. 124, No 1, 37--53.
• Ricardo Conceição
Gettysburg College
Definition and first properties of Markov polynomials
PDF abstract
Size: 75 kb
The sequence of Markov numbers (A002559 in the OEIS) $$1, 2, 5, 13, 29, 34, 89, 169,\ldots$$ is generated from the integral solutions of Markov's equation $x^2+y^2+z^2=3xyz.$ In this talk, we define a sequence of polynomials over a finite field ${\mathbb F}_q$, with $q\equiv 1\mod 4$, which is analogous to the sequence of Markov numbers. We discuss some recently discovered and conjectured properties of these so-called Markov polynomials.
• Claude Gravel
The Tutte Institute for Mathematics and Computing
Permutations with one cycle of maximal length, and output bits of maximal algebraic degree
PDF abstract
Size: 118 kb
Let $n\geq 3$ be an odd positive integer. We study a subset $A\subset S_{2^n}$ for which every element has four properties. Properties are: (I) no more than $2n$ bits are needed to describe a permutation in $A$, (II) the algebraic degree of all the $n$ output boolean functions is $n-1$; an element of $A$ takes $(a_0,\ldots,a_{n-1})=a\in\{0,1\}^{n}$ as an input and produces an output $(\varphi_{0}(a),\ldots,\varphi_{n-1}(a))\in\{0,1\}^{n}$ where $\varphi_{j}$ is a boolean function for $j\in\{0,\ldots,n-1\}$, (III) every permutation in $A$ has one cycle of length $2^n$, and (IV) the expected number of terms (products of the $a_i$'s) of the boolean functions $\varphi_{j}$ for $j\in\{0,\ldots,n-1\}$ is $O(2^{n-1})$. Every element in $A$ is associated to some irreducible polynomial $Q\in\mathbb{Z}_{2}[X]$ such that $\textrm{deg}(Q)=n$, and to an exponent $d\in\{n,\ldots, 2^{n}-2\}$; the output of an element $a\in\{0,1\}^{n}$ is computed by (1) the input $a$ be encoded as $P_{a}(X)=a_0+\ldots +a_{n-1}X^{n-1}$, (2) let $R_{a,0}(X)=P_{a}(X)$ and for $\ell\in\{1,\ldots,n\}$, let $R_{a,\ell}(X)=(R_{a,\ell-1}(X)+X^{d})^{-2^{\ell-1}}\mod Q(X)$, and (3) output the coefficients of $R_{a,n-1}(X)$. The cardinality of $A$ is smaller than $\frac{1}{n}\sum_{d\mid n}{2^{d}\mu(\frac{n}{d})}$ which is the number of irreducible polynomials of degree $n$. For a given $n$, characterizing polynomials that yields the four properties is my main goal together with proving the fourth property. Properties one and two are proven mathematically. Properties three and four are supported by symbolic computation with some yet unfigured steps for the proof of property three. I wish eventually to show that the ratio of the cardinality of $A$ and $\frac{1}{n}\sum_{d\mid n}{2^{d}\mu(\frac{n}{d})}\in O\big(\frac{2^n}{n}\big)$ is \emph{not} zero asymptotically with respect to $n$.
• Maria Chara
Instituto de Matemática Aplicada del Litoral (UNL-CONICET, Santa Fe, Argentina)
An Artin-Schreier tower of function fields in even characteristic
PDF abstract
Size: 74 kb
Let $\mathbb{F}_2$ be a finite field with two elements. In 2006 Beleen, Garcia and Stichtenoth proved that any recursive tower of function fields over $\mathbb{F}_2$, defined by $g(Y ) = f(X)$ with $g(T), f(T) \in {F}_2(T)$ and $\deg f = \deg g = 2$ is given by the Artin-Schreier equation $$Y^2 + Y =\frac{1}{(1/X)^2 + (1/X) + b}+ c$$ with $b, c \in \mathbb{F}_2$. They checked that all the posible cases were already considered in previous works, except when $b = c = 1$. In fact, they left as an open problem to determine whether this tower is asymptotically good or not over $\mathbb{F}_{2^s}$, for any positive integer $s$. In this talk we will discuss the asymptotic behavior of this tower.
• Christine Kelley
Multilevel coding and multistage decoding on partial erasure channels
PDF abstract
Size: 52 kb
Partial erasure channels have recently been introduced to model erasure events in applications such as flash memories. We show how multilevel coding and multistage decoding may be applied on different $q$-ary partial erasure channels for $q = p^k$, and classify when the subchannels are simple $p$-ary erasure channels. We show how to choose component codes to achieve channel capacity using multistage decoding in some cases. This is joint work with Carolyn Mayer and Kathryn Haymaker.
• Ariane Masuda
New York City College of Technology (New York City, United States)
Goppa Codes over Kummer extensions
PDF abstract
Size: 55 kb
We compute the Weierstrass semigroup at one totally ramified place for Kummer extensions defined by $y^m=f(x)^{\lambda}$ where $f(x)$ is a separable polynomial over $\mathbb{F}_q$. In addition, we compute the Weierstrass semigroup at two certain totally ramified places. Then we apply our results to construct one- and two-point Goppa codes with good parameters.
• Gretchen Mathews
Clemson University (South Carolina, United States)
AG codes as products of Reed-Solomon codes
PDF abstract
Size: 37 kb
In this talk, we consider families of algebraic geometry (AG) codes which can be expressed as products of Reed-Solomon codes and discuss applications.
• Daniel Katz
California State University, Northridge (Los Angeles, United States)
Valuations of Weil Sums of Binomials
PDF abstract
Size: 104 kb
Weil sums of binomials are finite field character sums that arise naturally in number theory and its technological applications. In cryptography, such sums determine the Walsh spectrum of a power permutation of a finite field, which measures its nonlinearity. Weil sums of binomials also determine the cross-correlation between two maximal linear sequences in digital sequence design and the weight distribution of certain cyclic error-correcting codes. Consider the Weil sum $W_{q,d}(a)=\sum_{x\in{\mathbf F}_q}\psi_q(x^d-ax),$ where \begin{itemize} \item $\psi_q$ is the canonical additive character of finite field ${\mathbf F}_q$, \item $\gcd(d,q-1)=1$, so that $x \mapsto x^d$ is a permutation of ${\mathbf F}_q$, \item $d$ is not a power of $p$ modulo $q-1$, to prevent $\psi_q(x^d-a x)$ degenerating to $\psi_q((1-a)x)$, and \item $a\in{\mathbf F}_q$. \end{itemize} Let $v_p$ be the $p$-adic valuation, and for fixed $q$ and $d$ let $V_{q,d} = \min_{a \in {\mathbf F}_q} v_p(W_{q,d}(a)),$ so that $V_{q,d}$ indicates the $p$-divisibility of the entire Walsh spectrum $\{W_{q,d}(a):a \in {\mathbf F}_q\}$. We present a proof that $V_{q,d}$ is never more than $2 n/3$, where $q=p^n$. We also present stronger upper bounds in special cases and discuss some conjectures. This is joint work with Philippe Langevin of Universit\'e de Toulon and Sangman Lee and Yakov Sapozhnikov of California State University, Northridge.
• Andreas Weingartner
Southern Utah University
The degree distribution of polynomial divisors over finite fields
PDF abstract
Size: 60 kb
We will describe a number of asymptotic estimates related to the degree distribution of polynomial divisors over finite fields, as well as analogous estimates concerning the distribution of integer divisors. Due to a very recent discovery of an explicit formula for the constant factor in these asymptotic estimates, we are now able to give numerical approximations of this factor. For example, the proportion of monic polynomials of degree $n$ over the field with two elements, which have a divisor of every degree up to $n$, is asymptotic to $3.400335...n^{-1}$ as $n$ grows.
• Jonathan Jedwab
A strong external difference family with more than two subsets
PDF abstract
Size: 59 kb
Strong external difference families (SEDFs) were introduced by Paterson and Stinson as a more restrictive version of external difference families. SEDFs can be used to produce optimal strong algebraic manipulation detection codes. We characterize the parameters $(v, m, k, \lambda)$ of a nontrivial SEDF that is near-complete (satisfying $v=km+1$). We construct the first known nontrivial example of a $(v, m, k, \lambda)$ SEDF having $m > 2$ subsets. The parameters of this example are $(243,11,22,20)$, giving a near-complete SEDF, and its group is $\mathbb{Z}_3^5$. The construction uses the point-orbits of the Mathieu group $M_{11}$ acting on the projective geometry PG$(4,3)$. This is joint work with Shuxing Li, Simon Fraser University.
• Lucia Moura
Ordered Orthogonal Array Construction Using LFSR Sequences
PDF abstract
Size: 80 kb
In this talk, we discuss a new construction of ordered orthogonal arrays (OOA) of strength $t$ with $(q + 1)t$ columns over a finite field $\mathbb{F}_{q}$ using linear feedback shift register sequences (LFSRs). OOAs are naturally related to $(t, m, s)$-nets, linear codes, and MDS codes. Our construction selects suitable columns from the array formed by all subintervals of length $\frac{q^{t}-1}{q-1}$ of an LFSR sequence generated by a primitive polynomial of degree $t$ over $\mathbb{F}_{q}$. The set of parameters of our OOAs are the same as the ones given by Rosenbloom and Tsfasman (1997) and Skriganov (2002), but the constructed arrays are different. We experimentally verify that our OOAs are stronger than the Rosenbloom-Tsfasman-Skriganov OOAs in the sense that ours are "closer'' to being a "full'' orthogonal array. We also discuss how our OOA construction relates to previous techniques to build OOAs from a set of linearly independent vectors over $\mathbb{F}_{q}$, as well as to hypergraph homomorphisms. This is joint work with André Castoldi (Brazil), Daniel Panario (Canada) and Brett Stevens (Canada), which recently appeared in IEEE Transactions on Information Theory vol. 68 (2017).
• David Thomson
Doubly-periodic Costas arrays
PDF abstract
Size: 67 kb
A \emph{Costas array} of order $n$ is a $n \times n$ permutation array (of $0$s and $1$s) where the vectors connecting any two $1$s are distinct. Costas arrays have optimal \emph{autocorrelation}; hence they have applications in, e.g., RADAR and SONAR systems and for digital communications. Costas arrays can equivalently be viewed as permutations $f$ on $[n] = \{0,1,\ldots,n-1\}$ such that for $d \in (0, n-1]$, $f(x+d)-f(x)$ are distinct for all $x \in [0,n-d-1]$. If the domain (respectively, codomain) of $f$ is instead considered to be $\mathbb{Z}/n\mathbb{Z}$, the Costas array is \emph{domain-periodic} (respectively, \emph{range-periodic}) modulo $n$; geometrically, consider the array wrapped around a vertical (respectively, horizontal) cylinder. It is known that no Costas array may be simultaneously domain- and range-periodic modulo $n$, though the classical Welch construction of Costas arrays provides a map that is domain-periodic modulo $p-1$ and range-periodic modulo $p$. We prove a 1993 conjecture of Golomb and Moreno that any array exhibiting the Welch style of dual-periodicity must be indeed be Welch. Doing so, we show the equivalent result that any polynomial $f\in \mathbb{F}_p[x]$ that satisfies: (1) $f(0) = 0$ and (2) $f(xd)-f(x)$ is a permutation for all $d \neq 1$, is a monomial permutation polynomial. We will also present some generalizations and related open-problems.
• Lisa Bromberg
United States Military Academy, West Pointe
Navigating in the Cayley graph of $\mathrm{SL}(2,\mathbb{F}_p)$ and applications to hashing
PDF abstract
Size: 73 kb
Hashing with matrices refers to a simple idea of using a pair of matrices, $A$ and $B$ (over a finite ring), to hash the "0" and "1" bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of matrices. Since there are many known pairs of $2 \times 2$ matrices over $\mathbb{Z}$ that generate a free monoid, this yields numerous pairs of matrices over $\mathbb{F}_p$, for sufficiently large primes $p$, that are candidates for collision-resistant hashing. However, this trick can "backfire", and lifting matrix entries to $\mathbb{Z}$ may facilitate finding a collision. This "lifting attack" was successfully used by Tillich and Zemor in the special case where two matrices $A$ and $B$ generate (as a monoid) the whole group $\mathrm{SL}_2(\mathbb{Z})$. However, in this paper we show that the situation with other, "similar", pairs of matrices from $\mathrm{SL}_2(\mathbb{Z})$ is different, and the "lifting attack" can (in some cases) produce collisions in the group generated by $A$ and $B$, but not in the positive monoid. Therefore, we argue that for these pairs of matrices, there are no known attacks at this time that would affect security of the corresponding hash functions. We also give explicit lower bounds on the length of collisions for hash functions corresponding to some particular pairs of matrices.
• Lucas Reis
Universidade Federal de Minas Gerais, Brazil
On the explicit factorization of $f(x^n)$ over finite fields.
PDF abstract
Size: 63 kb
Let $f(x)\in \mathbb F_q[x]$ be an irreducible polynomial of degree $k$ and exponent $e$ and $n$ be a positive integer such that $\text{rad}(n)$ divides $q-1$ and $\text{gcd}(ek, n)=1$. In this talk we discuss the explicit factorization of the polynomial $f(x^n)$ over $\mathbb F_q$. In particular, we apply our main result to certain classes of cyclotomic polynomials. This is a joint work with F.E. Brochero Martínez (Universidade Federal de Minas Gerais).
• Ivelisse Rubio
University of Puerto Rico (Río Piedras, Puerto Rico)
A refinement of a theorem of Carlitz
PDF abstract
Size: 60 kb
We refine some results of Carlitz about the existence of non-trivial solutions of polynomial equations in several variables $Y_1, \ldots, Y_n$ and coefficients in $F_q\left[X\right]$ by considering the $p$-weight degrees of the polynomials. We also present an extension of a theorem of Moreno and Moreno that gives a bound on the $p$-divisibility of the number of solutions of this type of systems.