On the pseudorandomness of automatic sequences

DOI10.1007/S12095-017-0260-7MaRDI QIDQ1667443zbMATH OpenOpenAlexFDO

Authors László Mérai, Arne Winterhof

Publication date 28 August 2018

Published in Cryptography and Communications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.03026

zbMATH Keywords

automatic sequencescorrelation measureThue-Morse sequencepseudorandom sequencesfinite automatonstate complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15) Pseudo-random numbers; Monte Carlo methods (11K45)

Abstract: We study the pseudorandomness of automatic sequences in terms of well-distribution and correlation measure of order 2. We detect non-random behavior which can be derived either from the functional equations satisfied by their generating functions or from their generating finite automatons, respectively.

Recommendations

• Pseudorandom sequences derived from automatic sequences
• scientific article; zbMATH DE number 3974332
• Publication:4727429
• On pseudorandom sequences and their application
• On Pseudorandom Sequences and Their Application
• Publication:5749362
• scientific article; zbMATH DE number 558650
• On a pseudorandom property of binary sequences
• Pseudo-randomness of a class of generalized self-shrinking sequences
• On the Autoreducibility of Random Sequences

Cites work

• scientific article; zbMATH DE number 1973372 (Why is no real title available?)
• Automatic Sequences
• Counting functions and expected values for the lattice profile at \(n\)
• Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets)
• Linear complexity and expansion complexity of some number theoretic sequences
• Measures of pseudorandomness
• Measures of pseudorandomness for finite sequences: typical values
• On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
• On finite pseudorandom binary sequences and their applications in cryptography
• On finite pseudorandom binary sequences. II: The Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction
• Pseudorandom sequences
• Subsequences of automatic sequences and uniform distribution
• Suites algébriques, automates et substitutions
• The Probabilistic Theory of Linear Complexity

Cited in

(11)

• Some Results on FCSR Automata With Applications to the Security of FCSR-Based Pseudorandom Generators
• scientific article; zbMATH DE number 4047127 (Why is no real title available?)
• On the maximum order complexity of Thue-Morse and Rudin-Shapiro sequences along polynomial values
• Automatic sequences: between determinism and randomness
• A Study on the Pseudorandom Properties of Sequences Generated Via the Additive Order
• On the Autoreducibility of Random Sequences
• Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin–Shapiro sequences
• Automaticity. IV: Sequences, sets, and diversity
• scientific article; zbMATH DE number 3843051 (Why is no real title available?)
• Pseudorandom sequences derived from automatic sequences
• Measures of pseudorandomness: arithmetic autocorrelation and correlation measure

This page was built for publication: On the pseudorandomness of automatic sequences

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