Mathematics Problem Archive

Can $\omega(n)$, the number of distinct prime factors of $n$, be computed in deterministic polynomial time?...

Let $C_{10}$ find $x$ satisfying $x^e\equiv a\pmod n$ under $\gcd(e,\varphi(n))=\gcd(a,n)=1$. Is complete integer factorization randomized polynomial-...

Can one decide in deterministic polynomial time whether a coprime integer $a$ is a square modulo a composite $n$?...

Is complete integer factorization randomized polynomial-time reducible to deciding quadratic residuosity modulo a composite?...

Given a prime $p$, can a quadratic nonresidue modulo $p$ be found in deterministic polynomial time?...

Given a sign vector $\varepsilon\in\{-1,1\}^k$, can the least prime $p$ satisfying $(p_i/p)=\varepsilon_i$ for every $i\le k$ be found in deterministi...

Given a prime $p$ and a quadratic residue $a$, can a square root $x^2\equiv a\pmod p$ be found in deterministic polynomial time?...

Given a prime $p$ and $f\in(\mathbb{Z}/p\mathbb{Z})[x]$ known to have a root, can a root be found in deterministic polynomial time?...

Given a prime $p$ and $f\in(\mathbb{Z}/p\mathbb{Z})[x]$, can the complete irreducible factorization of $f$ be found in deterministic polynomial time?...

Given a prime $p$ and degree $d$, can an irreducible polynomial of degree $d$ over $\mathbb{F}_p$ be constructed in deterministic polynomial time?...

Given a prime $p$ and $b$, can one decide in deterministic polynomial time whether $b$ generates $(\mathbb{Z}/p\mathbb{Z})^*$?...

Is recognition of primitive roots modulo a prime in randomized polynomial time $R$?...

Given a prime $p$, can a generator of $(\mathbb{Z}/p\mathbb{Z})^*$ be found in deterministic polynomial time?...

Given a prime $p$ and $a$ coprime to $p$, can $\operatorname{ord}_p(a)$ be computed in deterministic polynomial time?...

Given a prime $p$ and elements $g,b$ with $b$ in the subgroup generated by $g$, can an exponent $x$ satisfying $g^x\equiv b\pmod p$ be found in determ...

Given $g,b,n$ such that $g^x\equiv b\pmod n$ has a solution, can such an exponent $x$ be found in deterministic polynomial time?...

Is complete integer factorization deterministically polynomial-time reducible to discrete logarithms modulo composites?...

Is complete integer factorization deterministically polynomial-time reducible to computing $\varphi(n)$?...

Given $a,b$ and a prime $p$ with nonsingular curve $y^2=x^3+ax+b$, can a point on the curve modulo $p$ be found in deterministic polynomial time?...

Given $k,m,n$ with odd $n$ and $\gcd(km,n)=1$, can integers $x,y$ satisfying $x^2-ky^2\equiv m\pmod n$ be found in deterministic polynomial time?...

Is discrete logarithm modulo a prime randomized polynomial-time reducible to computing $g^{xy}$ from $g,g^x,g^y$?...

Given a prime $p$ and $n$, can one construct in deterministic polynomial time an elliptic curve over $\mathbb{F}_p$ having exactly $n$ points whenever...

Given an elliptic curve over $\mathbb{F}_p$ and points $P,Q$ such that $P=nQ$ for some $n$, can such an $n$ be found in deterministic polynomial time?...

For a full-rank integer lattice, is finding a nonzero vector of minimum Euclidean norm NP-hard?...

Does there exist a constant $c$ for which one can find in deterministic polynomial time a nonzero lattice vector of length at most $n^c$ times the min...

Given $f\in\mathbb{Q}[x]$, can the degree of its splitting field, equivalently the order of its Galois group, be computed in deterministic polynomial ...

Given $d\in\mathbb{N}$, can the class number $h(-d)$ of binary quadratic forms of discriminant $-d$ be computed in deterministic polynomial time?...

Under the promise that $b^2-4ac$ is not a square, is deciding whether $ax^2+bxy+cy^2+dx+ey+f=0$ has an integral solution NP-hard?...

Is the same binary quadratic Diophantine solvability problem NP-hard under randomized reductions?...

Can one decide in deterministic polynomial time whether $x^2-dy^2=-1$ has an integral solution?...

Can $\gcd(a,b)$ be computed in the parallel complexity class $NC$?...

Can two positive integers $a,b$ be multiplied using $O(\log(ab))$ bit operations?...

Is there an absolute upper bound for the size of a rational Diophantine $m$-tuple, a set of nonzero rationals for which the product of every two disti...

For each $n\in\{-3,3,5,8,12,20\}$, prove that no set of four distinct positive integers has property $D(n)$, meaning that every pairwise product plus ...

Let $U$ be the set of integers $n\not\equiv2\pmod4$ for which there are at most two distinct $D(n)$-quadruples. Is $U$ finite?...

For every nonzero integer $n$ that is not a square, are there only finitely many $D(n)$-quadruples?...

Determine the least positive integer $n_1$ and the greatest negative integer $n_2$ for which a $D(n_i)$-quintuple exists....

Are there infinitely many Diophantine triples that are also $D(n)$-triples for three distinct integers $n\ne1$?...

Does there exist a rational Diophantine septuple, that is, seven nonzero rational numbers whose pairwise products plus $1$ are rational squares?...

For which rational numbers $q$ do there exist infinitely many rational $D(q)$-quintuples?...

Does there exist a set of four nonzero rational numbers $\{a_1,a_2,a_3,a_4\}$ such that $a_i a_j+1$ is a rational square for every $1\le i,j\le4$, inc...

Let $P_n$ be the supremum of the sizes of nondegenerate polynomial $D(n)$-tuples over $\mathbb{Z}[X]$. Find an upper bound for $P_n$ depending only on...

Let $f\in\mathbb{Z}[X,Y]$ be a polynomial such that the equation $f(x,y)=0$ has only finitely many solutions $(x,y)\in \mathbb{Z}\times\mathbb{Z}$. Gi...

Let $k$ be a positive integer. The equation $$ x^p-y^q=k, $$ where the unknowns $x$, $y$, $p$ and $q$ take integer values, all $\ge 2$, has only finit...

There exists a positive number $C$ which depends only on $L$ and $H$ with the following property. Let $m$, $x$ and $y$ be rational integers with $m\ge...

Let $k\ge 2$ be an integer and $\alpha_1,\ldots,\alpha_n$ be non-zero elements in a field $K$ of zero characteristic, such that no quotient $\alpha_i/...

If there is no prime in the interval $[n+1,n+k]$, then the product $(n+1)\cdots(n+k)$ has at least $k$ distinct prime divisors....

Given an increasing sequence $n_1<n_2<\cdots<n_k$ of positive integers such that $n_1,n_2,\ldots,n_k$ are multiplicatively dependent, there exists a p...

Fix a positive integer $m$ for which the equation $$ m^2 + m_1^2 + m_2^2 = 3 mm_1m_2 $$ has a solution in positive integers $(m_1,m_2)$ with $0<m_1\le...

There exists a positive integer $k$ such that, for $m$ and $n$ positive integers, the conditions $$ R(m+i)=R(n+i)\quad (i=0,\ldots,k-1) $$ imply $m=n$...