A Galois field of the type $GF(p)$, where $p$ is prime, is normally expressed as the ring of integers modulo $p$.

If my understanding is correct, it is also possible to represent its elements as a ring $\mathbb Z_2[X]$ of polynomials defined over $GF(p)$, i.e. for $GF(2)$, we'd have polynomials of the form similar to $x^8+x^5+x^3+1$ or $x^9+x^6+x^2$, etc, and for $GF(5)$, we'd have polynomials of the form similar to $4*x^7+2*x^3+3*x+1$ or $2*x^5+3*x^3+x^2$, etc. All arithmetic operations are like with normal polynomials, but with a difference: all arithmetic operations on coefficients which occur in the calculations are done modulo $p$.

The question is: do polynomials defined over $GF(p)$ have any real application in cryptography where they are a better fit than their integers-modulo-$p$ counterparts?

Please correct me if I mixed something up in the theoretical part!

  • 2
    $\begingroup$ Lots of applications, including error correction and secret sharing. $\endgroup$ – Vadym Fedyukovych Jan 28 '15 at 17:06
  • $\begingroup$ Elements of $\mathrm{GF}(p^k)$ are usually represented as polynomials with coefficients in of $\mathrm{GF}(p)$. More generally, fields and polynomials are very closely related. $\endgroup$ – fkraiem Jan 28 '15 at 22:49

In my knowlegde, XTR is a cryptosystem build over $GF(p^6)$. We however use the subfield $GF(p^2)$ to have a compact representation. I don't know if there are other cryptosystems defined directly on Galois field extention, but using some tools are common. For that, take a look on the operative environment of Weil or Tate pairing.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.