Abstract
A class of periodic binary sequences that are obtained from the incidence vectors of hyperplanes in finite geometries is defined, and a general method to determine their linear spans (the length of the shortest linear recursion over GF(2) satisfied by the sequence) is described. In particular, we show that the projective and affine hyperplane sequences of odd order both have full linear span. Another application involves the parity sequence of order n, which has period p n − 1 and linear span vL(s) where v = (p n − 1)/(p − 1) and L(s) is the linear span of a parity sequence of order 1. The determination of the linear span of the parity sequence of order 1 leads to an interesting open problem involving primes.
This work was supported by the MITRE-Sponsored Research Program. A. H. Chan is also with the College of Computer Science, Northeastern University, Boston MA 02115
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
S. W. Golomb, “Shift Register Sequences,” Aegean Park Press, Laguna Hills, 1982.
J. L. Massey, Shift-Register Synthesis and BCH Decoding, IEEE Trans. Info TheoryIT-15 (1969), 122–127.
E. L. Key, An Analysis of the Structure and Complexity of Nonlinear Binary Sequence Generators, IEEE Trans. Info TheoryIT-22 (1976), 732–736.
R. A. Ruppel, “New Approaches to Stream Ciphers,” Ph.D. Thesis, Swiss Federal Institute of Technology, 1984.
N. Zieler, Linear Recurring Sequences, J. Soc. Indust. Appl. Math.7 (1959), 31–48.
R. A. Games, Crosscorrelation of M-sequences and GMW-sequences with the same primitive polynomial, Discrete Applied Math.12 (1985), 139–146.
J.M. Goethals and P. Delsarte, On a Class of Majority-logic Decodable Cyclic Codes, IEEE Trans. Info TheoryIT-14 (1968), 182–188.
F. J. MacWilliams and H.B. Mann, On the p-rank of the Design Matrix of a Difference Set, Info. Control12 (1968), 474–488.
K.J.C Smith, On the p-rank of the Incidence Matrix of Points and Hyperplanes in a Finite Projective Geometry, J. Combinatorial Theory7 (1969), 122–129.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chan, A.H., Games, R.A. (1987). On the Linear Span of Binary Sequences Obtained from Finite Geometries. In: Odlyzko, A.M. (eds) Advances in Cryptology — CRYPTO’ 86. CRYPTO 1986. Lecture Notes in Computer Science, vol 263. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47721-7_29
Download citation
DOI: https://doi.org/10.1007/3-540-47721-7_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18047-0
Online ISBN: 978-3-540-47721-1
eBook Packages: Springer Book Archive