Efficient Construction of Cross-Join Pairs in a Product of Primitive Polynomials of Pairwise-Coprime Degrees
Ming Li, Dongdai Lin · IEEE Transactions on Information Theory · 2021
We study the cross-join pairs in the cycles of linear feedback shift registers whose characteristic polynomials are of the form$l(x) = p_{1}(x)p_{2}(x)\cdots p_{k}(x)$, where$p_{i}(x), 1\leq i\leq k$are primitive polynomials of coprime degrees. Firstly, we use Coppersmithet al.’sgenerating function theory to derive the lower and upper bounds for the number of cross-join pairs. Then we design an algorithm to generate these cross-join pairs. The algorithm requires a preparatory phase which costs$O(2^{n'})$time where$n'$is the largest degree of$p_{i}(x), 1\leq i\leq k$, and after that it costs only$O(n^{3})$time to generate one cross-join pair where$n$is the degree of$l(x)$. We also consider a special class of cross-join pairs, for which the preparatory phase costs only$O(2^{n''})$time where$n''$is the second-largest degree of$p_{i}(x), 1\leq i\leq k$. The number of these special cross-join pairs is about$\frac {1}{12}2^{2n-n'}$. We present some experimental results, which validate our analysis and demonstrate the efficiencies of the algorithms. These cross-join pairs can be used in the cross-joining method to construct de Bruijn sequences.