Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSmall primitive roots and malleability of RSA moduli
198
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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$.
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.
We prove that $|x-y|ge 800X^{-4}$, where $x$ and $y$ are distinct singular moduli of discriminants not exceeding $X$. We apply this result to the primitive element problem for two singular moduli. In a previous article Faye and Riffaut show that the number field $mathbb Q(x,y)$, generated by two singular moduli $x$ and $y$, is generated by $x-y$ and, with some exceptions, by $x+y$ as well. In this article we fix a rational number $alpha e0,pm1$ and show that the field $mathbb Q(x,y)$ is generated by $x+alpha y$, with a few exceptions occurring when $x$ and $y$ generate the same quadratic field over $mathbb Q$. Together with the above-mentioned result of Faye and Riffaut, this gives a drastic generalization of a theorem due to Allombert et al. (2015) about solution of linear equations in singular moduli.
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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
