Search Results

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 …

Is it any easy to factor $p-1$ when $p$ is a prime compared to general factorization problem? What about when $2p+1$ is also a prime?

I have a system of $n=O(1)$ non-homogeneous polynomials of total degree $d=O(1)$ $p_1,\dots,p_r\in \mathbb Z[x_1,\dots,x_n]$. I would like to eliminate $n-1$ variables simultaneously from the $n$ poly …

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?

Consider the Linear Diophantine in known $a,b,c\in\mathbb Z$ $$ax+by=c.$$ Above can be solve by Extended Euclidean which is not in $NC$ as far as we know. It is clear if Extended Euclidean is in $NC$ …

Given an equation $x^2\equiv(a+ib)\bmod(c+id)$ where $a,b,c,d\in\mathbb Z$ holds, how to test if the equation has solutions and how to find the solutions in polynomial in $\log(|abcd|)$ time if $c+id$ …

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 …

Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime. If we already know t …

By $MRDP$ resolution of Hilbert's tenth, we infer, counting number of solutions to Diophantine equations is undecidable. Is parity of number of solutions to Diophantine equations undecidable?

There are many analogies between the objects $\mathbb F_q[x]$ and $\mathbb Z$. Supposing there is a fixed (say $10^9$) dimension linear integer program (describable without any objective function) in …

It is well known extracting modular square roots modulo a composite number factors the modulus. On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $NP$ …

Factorization is not known to have a polynomial time algorithm. Traditionally the input length is number of bits in representation of the integer to be factored. However now consider integers of form …

$LLL$ algorithm is vectorized version of Euclidean algorithm for $GCD$. Even the $m=2$ case known to Lagrange and Gauss does not have an $NC$ algorithm for shortest vector. If $GCD$ is in $NC$ and in …

Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$. Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$. Euclidean algorithm solves both. My question is if either 1 or 2 is i …

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$?