Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinite sets containing near-primitive roots
137
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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 $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.
Let $p=2n+1$ be an odd prime, and let $zeta_{p^2-1}$ be a primitive $(p^2-1)$-th root of unity in the algebraic closure $overline{mathbb{Q}_p}$ of $mathbb{Q}_p$. We let $ginmathbb{Z}_p[zeta_{p^2-1}]$ be a primitive root modulo $pmathbb{Z}_p[zeta_{p^2-1}]$ with $gequiv zeta_{p^2-1}pmod {pmathbb{Z}_p[zeta_{p^2-1}]}$. Let $Deltaequiv3pmod4$ be an arbitrary quadratic non-residue modulo $p$ in $mathbb{Z}$. By the Local Existence Theorem we know that $mathbb{Q}_p(sqrt{Delta})=mathbb{Q}_p(zeta_{p^2-1})$. For all $xinmathbb{Z}[sqrt{Delta}]$ and $yinmathbb{Z}_p[zeta_{p^2-1}]$ we use $bar{x}$ and $bar{y}$ to denote the elements $xmod pmathbb{Z}[sqrt{Delta}]$ and $ymod pmathbb{Z}_p[zeta_{p^2-1}]$ respectively. If we set $a_k=k+sqrt{Delta}$ for $0le kle p-1$, then we can view the sequence $$S := overline{a_0^2}, cdots, overline{a_0^2n^2}, cdots,overline{a_{p-1}^2}, cdots, overline{a_{p-1}^2n^2}cdots, overline{1^2}, cdots,overline{n^2}$$ as a permutation $sigma$ of the sequence $$S^* := overline{g^2}, overline{g^4}, cdots,overline{g^{p^2-1}}.$$ We determine the sign of $sigma$ completely in this paper.
Let $qgeq 1$ be any integer and let $ epsilon in [frac{1}{11}, frac{1}{2})$ be a given real number. In this short note, we prove that for all primes $p$ satisfying $$ pequiv 1pmod{q}, quad loglog p > frac{log 6.83}{frac{1}{2}-epsilon} mbox{ and } frac{phi(p-1)}{p-1} leq frac{1}{2} - epsilon, $$ there exists a quadratic non-residue $g$ which is not a primitive root modulo $p$ such that $gcdleft(g, frac{p-1}{q}right) = 1$.
By definition primitive and $2$-primitive elements of a finite field extension $mathbb{F}_{q^n}$ have order $q^n-1$ and $(q^n-1)/2$, respectively. We have already shown that, with minor reservations, there exists a primitive element and a $2$-primitive element $xi in mathbb{F}_{q^n}$ with prescribed trace in the ground field $mathbb{F}_q$. Here we amend our previous proofs of these results, firstly, by a reduction of these problems to extensions of prime degree $n$ and, secondly, by deriving an exact expression for the number of squares in $mathbb{F}_{q^n}$ whose trace has prescribed value in $mathbb{F}_q$. The latter corrects an error in the proof in the case of $2$-primitive elements. We also streamline the necessary computations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
