Search Results

Are there any software tools to find modular square roots of $y$ in $$x^2\equiv y\bmod p^t$$ where $p$ is a prime $\geq2$? Are there any special techniques which can speed up at $p=2$?

What is a good test for identifying cubic non-residues/residues and higher power non-residues/residues modulo a prime $R$ in terms of computational complexity? Given $M$ and $N$, is there a good way …

What is maximum $p\in(0,\frac12)$ such that if we know $2p\in(0,1)$ fraction of bits of $PQ$ with $P,Q$ primes it is possible to identify $p$ fraction of bits in each of $P,Q$ with certainty in polyno …

Given $m$ and $n$ in $\mathbb Z_{>0}$ what is the computational complexity of picking $n$ pairwise coprime integers each of $m$ bits when they exist? Given $m$ and $n$ in $\mathbb Z_{>0}$ what is the …

A post was made (Reduction from factoring to solving Pell equation) seeking clarification to solving $$x^2-Dy^2=1$$ to factoring when $D>0$. An answer was posted stating that to factor $N$, it suffice …

I have a $3$-variable linear Diophantine equation $$ax+by+cz=r$$ where $a,b,c,r\in\mathbb Z$ are known and can be as large in magnitude as needed and I know the equation has a solution $x,y,z\in\mathb …

If we take ceil and floor of $\sqrt{x(x+1)}$ (when it exists) we get $x$ and $x+1$ respectively. Is there an analog of this assuming roots exist in modular arithmetic (at least modulo primes)? Assumin …

In https://arxiv.org/abs/1009.3956 is it shown there is a $c>0$ such that $\pi(x)\bmod2$ can be computed in $o(x^{\frac12})$ time (more precisely number of primes $\bmod 2$ for an interval of length a …

Given $a,b\in\Bbb N$ where each $a,b$ is $n$-bits, we can compute $\mathsf{gcd}(a,b)$ in $cn^{1+\epsilon}$ bit operations for some fixed $c\geq1$. My query is given $N,a,b$ where $a,b$ is $n$-bits an …

Supposing the product form $n=\prod_{i=1}^np_i^{e_i}$ is given with every prime $p_i$ and integer $e_i$ known and given $d\in\Bbb Z$ and $h\in\Bbb Z_n$ with $g^d=h\bmod p$ what is the complexity of fi …

On page $8$ in these slides (http://www.math.unicaen.fr/~nitaj/LatticeMalaysia2014-2.pdf) it is told that if we want to solve $$x_1a_1+\dots+x_na_n=N$$ where $|x_i|<\frac{2^{n/4}N^\frac1{n+1}}{\sqrt n …

Is there a way to compute an $x$ satisfying $$x^2\equiv a\bmod(2^t-1)$$ where $a,t$ are integers given to us and factorization of $2^t-1$ is not given to us?

Given $a \in \mathbb{Z}$ with $a > 1$. Let $g(x) \in \mathbb{Z}[x]$ be a polynomial with $g(a)=\pm 1$. Let $h(x) \in \mathbb{Z}[x]$ be a polynomial with $h(a)= p$, a prime. Let $g(x)$ and $h(x)$ have …

Given a quaternary quadratic equation of form $$Q(a,b,c,d)=m$$ in $\Bbb Z[a,b,c,d]$ with coefficient sizes and $|m|$ bounded in magnitude by $B\in\Bbb N$ where $m\neq0$ if we are looking for solutions …

Given two primes $p,q\in[T,2T]$, how many integers $m$ of size $O(T^{3/2+\epsilon})$ are there such that the residues $m\bmod p$ and $m\bmod q$ are both $O(polylog(T))$? Looking for an answer Is it po …