Pseudorandom sequences derived from automatic sequences

DOI10.1007/s12095-022-00556-9zbMath1498.94049arXiv2105.03086OpenAlexW3162399915WikidataQ114849169 ScholiaQ114849169MaRDI QIDQ2154881

László Mérai, Arne Winterhof

Publication date: 15 July 2022

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

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

zbMATH Keywords

normality finite fields automatic sequences linear complexity pseudorandomness correlation measure expansion complexity well-distribution measure maximum order complexity

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Automata sequences (11B85)

Cites Work

Combinatorial constructions for the Zeckendorf sum of digits of polynomial values
On the limit distribution of the well-distribution measure of random binary sequences
Some properties of a Rudin-Shapiro-like sequence
Bits of $3^n$ in binary, Wieferich primes and a conjecture of Erdős
Expansion complexity and linear complexity of sequences over finite fields
The sum of digits of squares
Substitutions in dynamics, arithmetics and combinatorics
On the number of points on a complete intersection over a finite field. (Appendix: Number of points on singular complete intersections by Nicholas M. Katz)
Prime numbers along Rudin-Shapiro sequences
On the number of $N$-free elements with prescribed trace
On a problem of Gelfond: the sum of digits of prime numbers
Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
Ensembles presque périodiques $k$-reconnaissables. (Almost periodic $k$-recognizable sets)
Hankel determinants of the Thue-Morse sequence
On finite pseudorandom binary sequences. II: The Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction
Polynomial subsequences of certain automatic sequences
Lattice structure and linear complexity profile of nonlinear pseudorandom number generators
On the measures of pseudorandomness of binary sequences.
On the pseudorandomness of automatic sequences
Normality along squares
On the $N$th linear complexity of automatic sequences
Trace of products in finite fields
Prescribing digits in finite fields
On the sum of digits of special sequences in finite fields
Enumeration of factors in the Thue-Morse word
La conjecture de Weil. I
Cryptographic applications of analytic number theory. Complexity lower bounds and pseudo\-randomness
Sums of digits and almost primes
The sum of digits of polynomial values in arithmetic progressions
Prescribing the binary digits of primes
Perfect linear complexity profile and apwenian sequences
On enumeration of irreducible polynomials and related objects over a finite field with respect to their trace and norm
Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences
How to prove that a sequence is not automatic
On the maximum order complexity of Thue-Morse and Rudin-Shapiro sequences along polynomial values
Normality of the Thue-Morse function for finite fields along polynomial values
Algebraic dependence in generating functions and expansion complexity
On the $N$th maximum order complexity and the expansion complexity of a Rudin-Shapiro-like sequence
Polynomial values in affine subspaces of finite fields
Prescribing the binary digits of primes. II
Polynomial values and generators with missing digits in finite fields
Spectrum of a Rudin-Shapiro-like sequence
On the squares in the set of elements of a finite field with constraints on the coefficients of its basis expansion
Normality of the Thue-Morse sequence along Piatetski-Shapiro sequences. II
On the enumeration of irreducible polynomials over $\mathrm{GF}(q)$ with prescribed coefficients
On the subword complexity of Thue-Morse polynomial extractions
Counting functions and expected values for the lattice profile at $n$
The measures of pseudorandomness and the NIST tests
The correlation measures of finite sequences: limiting distributions and minimum values
Handbook of Finite Fields
The sum of digits function in finite fields
Applied Number Theory
Sequences With High Nonlinear Complexity
On digital blocks of polynomial values and extractions in the Rudin–Shapiro sequence
Some Theorems on Fourier Coefficients
Subsequences of automatic sequences and uniform distribution
NORMALITY OF THE THUE–MORSE SEQUENCE ALONG PIATETSKI-SHAPIRO SEQUENCES
TestU01
Recent Results on Recursive Nonlinear Pseudorandom Number Generators
Ternary expansions of powers of 2
The Probabilistic Theory of Linear Complexity
Suites algébriques, automates et substitutions
On finite pseudorandom binary sequences III: The Liouville function, I
Distribution des polynômes irréductibles dans $
On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
Automatic Sequences
The Rudin–Shapiro Sequence and Similar Sequences Are Normal Along Squares
Möbius orthogonality for the Zeckendorf sum-of-digits function
Rudin–Shapiro sequences along squares
On a Golay-Shapiro-Like Sequence
Sequences with almost perfect linear complexity profiles and curves over finite fields
Somme des chiffres et transcendance
Discrete correlations of order 2 of generalised Rudin-Shapiro sequences: a combinatorial approach
On the Maximum Order Complexity of the Thue-Morse and Rudin-Shapiro Sequence
The level of distribution of the Thue–Morse sequence
On the distribution of the Rudin-Shapiro function for finite fields
On the use of expansion series for stream ciphers
Trace of Products in Finite Fields from a Combinatorial Point of View
Ideals, Varieties, and Algorithms
Linear Complexity and Expansion Complexity of Some Number Theoretic Sequences
Prescribing the binary digits of squarefree numbers and quadratic residues
On the Expansion Complexity of Sequences Over Finite Fields
Irreducible Polynomials Over a Finite Field with Restricted Coefficients
On subwords in the base-$q$ expansion of polynomial and exponential functions
Measures of pseudorandomness for finite sequences: typical values
Progress in Cryptology - INDOCRYPT 2003
Sur les nombres qui ont des propriétés additives et multiplicatives données
Irreducible polynomials with several prescribed coefficients
Irreducible polynomials with several prescribed coefficients
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item

This page was built for publication: Pseudorandom sequences derived from automatic sequences