Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuadratic non-residues and non-primitive roots satisfying a coprimality condition
135
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
We present a short, self-contained, and purely combinatorial proof of Linniks theorem: for any $varepsilon > 0$ there exists a constant $C_varepsilon$ such that for any $N$, there are at most $C_varepsilon$ primes $p leqslant N$ such that the least positive quadratic non-residue modulo $p$ exceeds $N^varepsilon$.
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 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.
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 $p>3$ be a prime, and let $(frac{cdot}p)$ be the Legendre symbol. Let $binmathbb Z$ and $varepsilonin{pm 1}$. We mainly prove that $$left|left{N_p(a,b): 1<a<p text{and} left(frac apright)=varepsilonright}right|=frac{3-(frac{-1}p)}2,$$ where $N_p(a,b)$ is the number of positive integers $x<p/2$ with ${x^2+b}_p>{ax^2+b}_p$, and ${m}_p$ with $minmathbb{Z}$ is the least nonnegative residue of $m$ modulo $p$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
