On Finite Pseudorandom Binary Sequences II. The Champernowne, Rudin-Shapiro, and Thue-Morse Sequences, A Further Construction

摘要

Special finite binary sequences are tested for pseudorandomness. As measures of pseudorandomness, well-distribution relative to arithmetic progressions and small (auto) correlation are used. These properties of the Champernowne, Thue-Morse, and Rudin-Shapiro sequences are studied and it is shown that although each of them possesses certain pseudorandom properties, none of them can be considered completely pseudorandom. Finally, by using the Legendre symbol and permutation polynomials, a nearly ideally pseudorandom sequence is constructed.