Binary Sequences Derived From Differences of Consecutive Primitive Roots

DOI10.1109/TIT.2021.3088143zbMATH Open1486.11155arXiv2105.08003OpenAlexW3170761584MaRDI QIDQ4958230FDOQ4958230

Zibi Xiao, Arne Winterhof

Publication date: 7 September 2021

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Let $1<g_1<ldots<g_{varphi(p-1)}<p-1$ be the ordered primitive roots modulo~$p$. We study the pseudorandomness of the binary sequence $(s_n)$ defined by $$, $n=0,1,ldots$. In particular, we study the balance, linear complexity and $2$-adic complexity of $(s_n)$. We show that for a typical $p$ the sequence $(s_n)$ is quite unbalanced. However, there are still infinitely many $p$ such that $(s_n)$ is very balanced. We also prove similar results for the distribution of longer patterns. Moreover, we give general lower bounds on the linear complexity and $2$-adic complexity of~$(s_n)$ and state sufficient conditions for attaining their maximums. Hence, for carefully chosen $p$, these sequences are attractive candidates for cryptographic applications.

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

zbMATH Keywords

balancelower boundslinear complexity2-adic complexitypseudorandomness of binary sequence

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Pseudo-random numbers; Monte Carlo methods (11K45)

Cited In (4)

• Balance and pattern distribution of sequences derived from pseudorandom subsets of \(\mathbb{Z}_q\)
• Balance, pattern distribution and linear complexity of \(M\)-ary sequences from Sidel'nikov sequences
• Binary sequences derived from differences of consecutive quadratic residues
• On the Distinctness of Binary Sequences Derived From Primitive Sequences Modulo Square-Free Odd Integers

This page was built for publication: Binary Sequences Derived From Differences of Consecutive Primitive Roots

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