Counting coprime polynomials... with complications

Abstract

The construction of coprime 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 way to count and enumerate coprime polynomial pairs based on what they call DilcuE’s algorithm (i.e., Euclid’s algorithm ran backwards). In this talk, we consider a specific case of the above problem, namely when both polynomials have the same degree and a nonzero constant term, which is motivated by the design of secret sharing schemes via cellular automata. Interestingly, this variant turns out to be more complicated, requiring different approaches ranging from formal languages to combinatorics to solve different aspects of the problem. In particular, we decompose our problem in two parts. First, we show that the sequences of constant terms for the quotients visited by DilcuE’s algorithm can be modeled as words of a regular language recognized by a simple finite state automaton. This allows us in turn to count all such sequences by leveraging on classic results from algebraic language theory. On the other hand, we show that the sequences of degrees of quotients in DilcuE’s algorithms are equivalent to compositions of natural numbers, which have a simple description in terms of partially ordered sets. Putting these two results together, we finally devise a combinatorial algorithm that enumerates all pairs of coprime polynomials with nonzero constant term of given degree.