Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCorrelation measures of binary sequences derived from Euler quotients
73
0
0.0
(
0
)
Added by
Zhixiong Chen
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Fermat-Euler quotients arose from the study of the first case of Fermats Last Theorem, and have numerous applications in number theory. Recently they were studied from the cryptographic aspects by constructing many pseudorandom binary sequences, whose linear complexities and trace representations were calculated. In this work, we further study their correlation measures by using the approach based on Dirichlet characters, Ramanujan sums and Gauss sums. Our results show that the $4$-order correlation measures of these sequences are very large. Therefore they may not be suggested for cryptography.
rate research
Read More
For a prime $pge 5$ let $q_0,q_1,ldots,q_{(p-3)/2}$ be the quadratic residues modulo $p$ in increasing order. We study two $(p-3)/2$-periodic binary sequences $(d_n)$ and $(t_n)$ defined by $d_n=q_n+q_{n+1}bmod 2$ and $t_n=1$ if $q_{n+1}=q_n+1$ and $t_n=0$ otherwise, $n=0,1,ldots,(p-5)/2$. For both sequences we find some sufficient conditions for attaining the maximal linear complexity $(p-3)/2$. Studying the linear complexity of $(d_n)$ was motivated by heuristics of Caragiu et al. However, $(d_n)$ is not balanced and we show that a period of $(d_n)$ contains about $1/3$ zeros and $2/3$ ones if $p$ is sufficiently large. In contrast, $(t_n)$ is not only essentially balanced but also all longer patterns of length $s$ appear essentially equally often in the vector sequence $(t_n,t_{n+1},ldots,t_{n+s-1})$, $n=0,1,ldots,(p-5)/2$, for any fixed $s$ and sufficiently large $p$.
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 $s_nequiv g_{n+1}+g_{n+2}bmod 2$, $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.
A new method is used to resolve a long-standing conjecture of Niho concerning the crosscorrelation spectrum of a pair of maximum length linear recursive sequences of length $2^{2 m}-1$ with relative decimation $d=2^{m+2}-3$, where $m$ is even. The result indicates that there are at most five distinct crosscorrelation values. Equivalently, the result indicates that there are at most five distinct values in the Walsh spectrum of the power permutation $f(x)=x^d$ over a finite field of order $2^{2 m}$ and at most five distinct nonzero weights in the cyclic code of length $2^{2 m}-1$ with two primitive nonzeros $alpha$ and $alpha^d$. The method used to obtain this result proves constraints on the number of roots that certain seventh degree polynomials can have on the unit circle of a finite field. The method also works when $m$ is odd, in which case the associated crosscorrelation and Walsh spectra have at most six distinct values.
In this short note, we reformulate the task of calculating the pair correlation statistics of a Kronecker sequence as a lattice point counting problem. This can be done analogously to the lattice based approach which was used to (re-)prove the famous three gap property for Kronecker sequences. We show that recently developed lattice point counting techniques can then be applied to derive that a certain class of Kronecker sequences have $beta$-pair correlations for all $0 < beta < 1$.
In 2009, Grant, Shallit, and Stoll constructed a large family of pseudorandom sequences, called generalized Rudin--Shapiro sequences, for which they established some results about the average of discrete correlation coefficients of order 2 in cases where the size of the alphabet is a prime number or a squarefree product of primes. We establish similar results for an even larger family of pseudorandom sequences, constructed via difference matrices, in the case of an alphabet of any size. The constructions generalize those from Grant et al. In the case where the size of the alphabet is squarefree and where there are at least two prime factors, we obtain an improvement in the error term by comparison with the result of Grant et al.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
