Abstract
For a Galois field GF(2 ^{n}) defined by a primitive element α with minimal polynomial f, the index table contains in row i the coordinates of α ^{i} in the polynomial basis α ^{n1}, α ^{n2},..., α, 1. Each column i in this table equals the msequence with characteristic polynomial f, shifted cyclically by some offset h _{i}. In this paper we show that the set of the n shifts h _{i} contains large subsets which are modular Golomb rulers modulo 2 ^{n} 1 (i.e. all the differences are different). Let D be the set of integers j such that the coefficient of x ^{j} in f is nonzero. We prove that the set H _{D} of shifts corresponding to columns j ∈ D can be partitioned into two subsets (the columns in the left half of the table and the ones in the right half) each of which is a modular Golomb ruler. Based on this result and on computational data, we conjecture that in fact the whole set H _{D} is a modular Golomb ruler. We give a polynomial time algorithm for deciding if given a subset of column positions, the corresponding shifts are a modular Golomb ruler. These results are applied to filter generators used in the design of stream ciphers. Golić recommends that in order to withstand his inversion attack, one of the design requirements should be that the inputs of the nonlinear filtering function are taken from positions of a Fibonacci LFSR which form a Golomb ruler. We propose using a Galois LFSR instead and selecting positions such that the corresponding shifts form a modular Golomb ruler. This would allow for a larger number of inputs to be selected (roughly n/2 rather than √2n) while still satisfying Golić's requirement.
Original language  English 

Title of host publication  Sequences and Their Applications, SETA 2012  7th International Conference, Proceedings 
Pages  136147 
Number of pages  12 
DOIs  
Publication status  Published  2012 
Externally published  Yes 
Event  International Conference on Sequences and their Applications 2012  Waterloo, Canada Duration: 4 Jun 2012 → 8 Jun 2012 Conference number: 7th https://link.springer.com/book/10.1007/9783642306150 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 

Volume  7280 LNCS 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  International Conference on Sequences and their Applications 2012 

Abbreviated title  SETA 2012 
Country/Territory  Canada 
City  Waterloo 
Period  4/06/12 → 8/06/12 
Internet address 
