Skip to main content

All Questions

Filter by
Sorted by
Tagged with
4 votes
0 answers
311 views

Possible $\mathsf{NP}$ complete problem from number theory

A candidate $\mathsf{NP}$ complete variant of factoring was posted in https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring, where decision problem $\text{BOUNDED-...
Turbo's user avatar
  • 13.9k
2 votes
1 answer
538 views

Modular square roots problem which is $NP$ hard

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 $...
Turbo's user avatar
  • 13.9k
1 vote
0 answers
70 views

Is this factorization problem in EXP?

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 $...
Turbo's user avatar
  • 13.9k