Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBinary Sequences Derived from Differences of Consecutive Primitive Roots
139
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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 $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.
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$.
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.
Fix $a in mathbb{Z}$, $a otin {0,pm 1}$. A simple argument shows that for each $epsilon > 0$, and almost all (asymptotically 100% of) primes $p$, the multiplicative order of $a$ modulo $p$ exceeds $p^{frac12-epsilon}$. It is an open problem to show the same result with $frac12$ replaced by any larger constant. We show that if $a,b$ are multiplicatively independent, then for almost all primes $p$, one of $a,b,ab, a^2b, ab^2$ has order exceeding $p^{frac{1}{2}+frac{1}{30}}$. The same method allows one to produce, for each $epsilon > 0$, explicit finite sets $mathcal{A}$ with the property that for almost all primes $p$, some element of $mathcal{A}$ has order exceeding $p^{1-epsilon}$. Similar results hold for orders modulo general integers $n$ rather than primes $p$.
In a paper of P. Paillier and J. Villar a conjecture is made about the malleability of an RSA modulus. In this paper we present an explicit algorithm refuting the conjecture. Concretely we can factorize an RSA modulus n using very little information on the factorization of a concrete n coprime to n. However, we believe the conjecture might be true, when imposing some extra conditions on the auxiliary n allowed to be used. In particular, the paper shows how subtle the notion of malleability is.
Let tau(.) be the Ramanujan tau-function, and let k be a positive integer such that tau(n) is not 0 for n=1,...,[k/2]. (This is known to be true for k < 10^{23}, and, conjecturally, for all k.) Further, let s be a permutation of the set {1,...,k}. Then there exist infinitely many positive integers m such that |tau(m+s(1))|<tau(m+s(2))|<...<|tau(m+s(k))|. We also obtain a similar result for Fourier-coefficients of general newforms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
