I am wondering if the inversion of multiplication of polynomials is equally hard as the discrete logarithm problem used for key exchange. Or are there algorithms that weaken such an usage. I understand that it is somewhat easy to factorize if one omits the division by an irreducible polynomial.

I cannot find any comparison for the hardness of

  • multiplicative inverse in GF(2^n) mod (some irreducible polynomial)
  • Diffie Hellman using exponents of g^x mod p
  • elliptic curves

Only for the last two I was able to find some comparison which favors elliptic curves over the discrete logarithm problem as the key length is about 1/12 as opposed to Diffie Hellman for the same security.

  • $\begingroup$ What is "the hardness of elliptic curves" supposed to mean? $\endgroup$
    – fkraiem
    Commented Aug 19, 2018 at 4:05

1 Answer 1


The inverse is easy, it can be done by the extended Euclidean algorithm, thus polynomial in complexity compared to the others which are exponential.

  • $\begingroup$ Okay, I understand. Due to my lack of imagination that such thing would work on a mod p, I did not know such things work. But yes, even Wikipedia tells about this. $\endgroup$
    – kwasmich
    Commented Aug 19, 2018 at 8:18
  • $\begingroup$ So if I get it right. I have to use Diffie Hellman or Elliptic Curves to get the level of security. But can do both in GF(2^n) ? $\endgroup$
    – kwasmich
    Commented Aug 19, 2018 at 8:26
  • 1
    $\begingroup$ That's a separate question but DH and elliptic curves are strongest in large prime fields, not extension fields. $\endgroup$
    – kodlu
    Commented Aug 19, 2018 at 10:08
  • $\begingroup$ See this crypto.stackexchange.com/questions/48153/… $\endgroup$
    – kodlu
    Commented Aug 19, 2018 at 10:11
  • $\begingroup$ I am a novice in the field of cryptography. So I don't know if I get the things right. To my understanding an extension field is for example $GF(2^8) \mod{m}$ where $m=x^8+x^4+x^3+x+1$ which is the smallest irreducible polynomial outside of $GF(2^8)$ (which is somewhat like a prime in $GF()$). And $GF(p)$ with $p$ prime do I still need a $\mod{m}$ to wrap the values back into the field or is $m = p$ sufficient? Or is it only the case if $p$ is prime in $\mathbb{Z}$ and also forms an irreducible polynomial in $GF$. $\endgroup$
    – kwasmich
    Commented Aug 19, 2018 at 13:46

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.