Score:1

Can some cryptographic conclusions in the prime field be applied to the Galois field?

vg flag

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?

Score:1
sa flag

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.

poncho avatar
my flag
Actually $NP \ne coNP$ (which appears likely) would imply that DL is *not* NP hard...
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.