2
$\begingroup$

Sieve techniques apply to integer factoring and discrete logarithm to provide $2^{O(((\log n)(\log\log n)^2)^{1/3})}$ complexity for $n$ bit factoring and $n$ bit prime discrete logarithm.

The state of the art has not budged in a generation.

Is there evidence which indicates sieve techniques cannot be improved further?

$\endgroup$
1
  • $\begingroup$ @johncoleman Makes no sense to relate to $\mathsf{P}=\mathsf{NP}$. There could be a different structurally different algorithm. Sieve algorithms do not speed-up $\mathsf{NP}$-complete problems. $\endgroup$
    – Turbo
    Commented Jan 10, 2021 at 13:32

0

You must log in to answer this question.