Pseudorandom binary sequences: quality measures and number-theoretic constructions

2023/05/19 by Arne Winterhof, Winterhof, Arne · 1 citation
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Coding theory and cryptography #Computability, Logic, AI Algorithms #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2305.11486

openalex publication_date 2023/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this survey we summarize properties of pseudorandomness and non-randomness of some number-theoretic sequences and present results on their behaviour under the following measures of pseudorandomness: balance, linear complexity, correlation measure of order k, expansion complexity and 2-adic complexity. The number-theoretic sequences are the Legendre sequence and the two-prime generator, the Thue-Morse sequence and its sub-sequence along squares, and the prime omega sequences for integers and polynomials.

Cited by

• On the Nth 2-adic complexity of binary sequences identified with algebraic 2-adic integers

Related

• Pseudorandom sequences derived from automatic sequences
• On the pseudorandomness of Parry--Bertrand automatic sequences
• Families of sequences with good family complexity and cross-correlation measure
• The measures of pseudorandomness and the NIST tests
• On the pseudorandomness of automatic sequences