On the joint 2-adic complexity of binary multisequences

DOI10.1051/ITA/2012011MaRDI QIDQ2905327zbMATH OpenOpenAlexFDO

Authors Lu Zhao, Qiaoyan Wen

Publication date 27 August 2012

Published in RAIRO. Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2012__46_3_401_0/, https://eudml.org/doc/222028

zbMATH Keywords

cryptographyFCSRFourier transformjoint 2-adic complexitystream cipher

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Cryptography (94A60)

Review text

In [\textit{M. Goresky} et al., IEEE Trans. Inf. Theory 46, No. 2, 687--691 (2000; Zbl 0996.94029)] the 2-adic complexity of a binary sequence has been related to the number of nonzero classical Fourier coefficients of the sequence. In this article the authors adapt the Fourier transform in the obvious way for multisequences, and convert the upper bound for the 2-adic complexity given in [loc. cit.] to the corresponding bound for the joint 2-adic complexity of a multisequence. Using the known relations between Fourier coefficients, it is pointed out in Theorem 3.5 that the bounds can be expressed using the factorization of the period length \(L\) (\(L\) odd) of the sequence. (The formulation of the theorem is misleading, differently than claimed an upper bound is not given there, solely the shape of the bound in Theorem 3.3 is explained.) The paper finishes with a description of an upper bound for the number of \(p^n\)-periodic multisequences with given joint 2-adic complexity, \(p>2\) prime.

Recommendations

• 2-Adic Complexity of Binary m-Sequences
• On the Expected Value of the Joint 2-Adic Complexity of Periodic Binary Multisequences
• A fast algorithm for the 2-adic joint complexity of p^n-periodic binary multisequence
• 2-adic complexity of binary sequences with interleaved structure
• A New Method to Compute the 2-Adic Complexity of Binary Sequences
• On the 2-Adic Complexity and the k-Error 2-Adic Complexity of Periodic Binary Sequences
• On the 2-Adic Complexity and the k-Error 2-Adic Complexity of Periodic Binary Sequences
• On the 2-Adic Complexity of the Ding-Helleseth-Martinsen Binary Sequences
• 2-adic complexity of two classes of generalized cyclotomic binary sequences
• The 2-adic complexity of a class of binary sequences with optimal autocorrelation magnitude

Cites work

• A lower bound on the linear span of an FCSR
• Error linear complexity measures for multisequences
• Feedback shift registers, 2-adic span, and combiners with memory
• Fourier transforms and the 2-adic span of periodic binary sequences
• Joint linear complexity of multisequences consisting of linear recurring sequences
• Linear complexity, \(k\)-error linear complexity, and the discrete Fourier transform
• On the Expected Value of the Joint 2-Adic Complexity of Periodic Binary Multisequences
• The expected value of the joint linear complexity of periodic multisequences

Cited in

(5)

• On lattice-based algebraic feedback shift registers synthesis for multisequences
• Solving the FCSR synthesis problem for multi-sequences by lattice basis reduction
• A fast algorithm for the 2-adic joint complexity of p^n-periodic binary multisequence
• On the Expected Value of the Joint 2-Adic Complexity of Periodic Binary Multisequences
• FCSR periodic multisequences with maximal joint N-adic complexity and large k-error joint N-adic complexity over Z/(N)

This page was built for publication: On the joint 2-adic complexity of binary multisequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2905327)