Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBinary sequences derived from differences of consecutive quadratic residues
440
0
0.0
(
0
)
Added by
Zibi Xiao
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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.
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.
Let $p$ be a large prime, and let $kll log p$. A new proof of the existence of any pattern of $k$ consecutive quadratic residues and quadratic nonresidues is introduced in this note. Further, an application to the least quadratic nonresidues $n_p$ modulo $p$ shows that $n_pll (log p)(log log p)$.
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 paper we study products of quadratic residues modulo odd primes and prove some identities involving quadratic residues. For instance, let $p$ be an odd prime. We prove that if $pequiv5pmod8$, then $$prod_{0<x<p/2,(frac{x}{p})=1}xequiv(-1)^{1+r}pmod p,$$ where $(frac{cdot}{p})$ is the Legendre symbol and $r$ is the number of $4$-th power residues modulo $p$ in the interval $(0,p/2)$. Our work involves class number formula, quartic Gauss sums, Stickelbergers congruence and values of Dirichlet L-series at negative integers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
