1
$\begingroup$

SUBEXP is defined as the intersection of DTIME(2^n^c) over all c>0. The order of the Quadratic Sieve algorithm is O(exp((k+o(1))(logN)^1/2(loglogN)^1/2)). Doesn't this imply that the decision version of integer factorization is in SUBEXP? I ask because I can't find this result anywhere and I find it interesting since I believe (correct me if I'm wrong) that being in SUBEXP is better than being in NP in the sense that problems being in the first class are easier to solve.

$\endgroup$
1
  • $\begingroup$ You can use mathjax to make your question more readable, e.g. $2^{n^c}$. $\endgroup$
    – lamontap
    Apr 19 at 13:41

1 Answer 1

1
$\begingroup$

Yes both QS and NFS (Number Field Sieve) imply that factorization is subexponential.

But the exact relationship between SUBEXP and NP is unknown. See the answer to the question here. And as pointed out in the comment by @fgrieu, the standard definition of security only calls for super-polynomial growth in the security parameter.

$\endgroup$
1
  • 1
    $\begingroup$ Addition: the standard definition of security only calls for super-polynomial (work grows faster than any polynomial of the security parameter) and that's believed compatible with subexponential (work grows slower than any stritcly increasing exponential of the security parameter): it's believed there are security classes in-between, and that QS/NFS fall into these. $\endgroup$
    – fgrieu
    Apr 18 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.