  We consider the problem of exhaustively visiting all pairs of linear cellular
automata which give rise to orthogonal Latin squares, i.e., linear Orthogonal
Cellular Automata (OCA). The problem is equivalent to enumerating all pairs of
coprime polynomials over a finite field having the same degree and a nonzero
constant term. While previous research showed how to count all such pairs for a
given degree and order of the finite field, no practical enumeration algorithms
have been proposed so far. Here, we start closing this gap by addressing the
case of polynomials defined over the field $\F_2$, which corresponds to binary
CA. In particular, we exploit Benjamin and Bennett's bijection between coprime
and non-coprime pairs of polynomials, which enables us to organize our study
along three subproblems, namely the enumeration and count of: (1) sequences of
constant terms, (2) sequences of degrees, and (3) sequences of intermediate
terms. In the course of this investigation, we unveil interesting connections
with algebraic language theory and combinatorics, obtaining an enumeration
algorithm and an alternative derivation of the counting formula for this
problem.
