1
$\begingroup$

Such as integer factorization problem and discrete logarithm problem. Assuming a large polynomial is obtained by multiplying two generated polynomials, is it NP hard to decompose it into these two generated polynomials ? And Assuming that A is the generator of the Galois field and B is a random number, is it NP hard to find an x to make $A^x=B$ hold?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Even the integer Discrete Log (DL) is not known to be NP complete. As pointed out in the comment by @poncho, $NP\neq coNP$ which may well be the case would imply that DL is not NP-hard.

Its exact hardness is unknown. And of course the Merkle-Hellman knapsack public key cryptosystem was based on an NP-hard problem but it was broken.

Regarding the finite field DL (see the detailed answer here): for some settings its complexity is quasi polynomial, otherwise it can be subexponential but superpolynomial.

For characteristic 2, see this question here.

For polynomial factorization over finite fields there is Berlekamp's Algorithm, and its later improvements.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Actually $NP \ne coNP$ (which appears likely) would imply that DL is not NP hard... $\endgroup$
    – poncho
    Commented Apr 18, 2023 at 18:27

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.