# Galois Field multiplication instead of Diffie Hellmans discrete logarithm

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.

• What is "the hardness of elliptic curves" supposed to mean? Commented Aug 19, 2018 at 4:05

## 1 Answer

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

• 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. Commented Aug 19, 2018 at 8:18
• 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) ? Commented Aug 19, 2018 at 8:26
• That's a separate question but DH and elliptic curves are strongest in large prime fields, not extension fields. Commented Aug 19, 2018 at 10:08
• Commented Aug 19, 2018 at 10:11
• 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$. Commented Aug 19, 2018 at 13:46