Enumerating coprime polynomials over GF(2) with nonzero constant term

Abstract

The construction of relatively prime polynomials over finite fields has several applications in cryptography, coding theory and combinatorics. In the binary field $GF(2)$, Benjamin and Bennett showed a simple bijection between coprime/non-coprime polynomial pairs based on what they call DilcuE’s algorithm (i.e., Euclid’s algorithm ran backwards). This allows one to easily construct a pair of coprime polynomials starting from a non-coprime one by executing Euclid’s algorithm as usual, change the last remainder to 1, and then go backward with DilcuE’s algorithm by applying the same sequence of quotients. In this talk, we consider a specific case of the above problem, namely the enumeration of coprime polynomials over $GF(2)$ where both polynomials have the same degree and a nonzero constant term, motivated by the construction of orthogonal Latin squares through linear cellular automata (CA). We decompose our problem of interest in two parts. The first part consists in enumerating the sequences of constant terms for the quotients visited by DilcuE’s algorithm. We show that such sequences form a regular language recognized by a finite state automaton, whose transitions are described by a De Bruijn graph. Then, we employ classic results from algebraic language theory to determine the generating function of this regular language, and derive the corresponding closed-form recurrence to count the number of all sequences of fixed length. The second part concerns the enumeration of the remaining coefficients in the quotients generated by DilcuE’s algorithm. We show that this is equivalent to enumerate all compositions of the polynomials’ degree. Putting everything together, we finally devise a combinatorial algorithm that enumerates all pairs of coprime polynomials with nonzero constant term, by independently generating all sequences of constant terms and compositions.