Re: Shamir sharing and GF(2^n)

Peter S. May <psmay@xxxxxxxxxxxx> wrote:

All right, so despite still being a little foggy on the specifics of
GF(2^n), once everything was abstracted out I managed to put together
a nice (t,n) secret sharing mechanism for t < 256 (using GF(2^8)), and
it looks adaptable to GF(2^16), provided I can find an irreducible
polynomial that works. (A doc I found about Reed-Solomon coding
suggested x^8 + x^5 + x^3 + x^2 + 1, rendered as 100101101b =3D 301,
and it works, but I'm still not sure how to construct an irreducible
polynomial for a given field. Any suggestions?)

I used x^8 + x^4 + x^3 + x^2 + 1, (0x11d) which I think is the
`smallest' (in the obvious ordering) primitive binary polynomial of
degree 8.

What's a primitive polynomial? Well, if p(x) is primitive of degree d,
and you represent F = GF(2^d) as GF(2)[x]/(p(x)) then x generates the
multiplicative group F^*. Huh? It means that you can represent every
the field element except 0 as a power of x. This is handy if you're
building log tables to do the arithmetic because it means there's an
obvious base to use for the logs.

I actually cribbed that polynomial from the Twofish design: it's the
polynomial they used for the MDS matrix multiply. I now have a (rather
grim) little utility program which finds primitive polynomials. For
GF(2^16), it suggests x^16 + x^5 + x^3 + x^2 + 1 (0x1002d).

Page 161 of the Handbook of Applied Cryptography (Menezes, van Oorschot
and Vanstone, CRC Press, http://www.cacr.math.uwaterloo.ca/hac/) has a
big table of primitive polynomials over GF(2).

-- [mdw]
.

Relevant Pages

  • Re: Primitive polynomials over GF(2^m)
    ... I am dealing with error correction codes for telecommunication. ... if we have a field extension L/K and alpha is an element of L ... definition about primitive polynomials in this book. ...
    (sci.math)
  • Re: Primitive polynomials over GF(2^m)
    ... extension field, and the definition given above is equivalent to that. ... coefficients" is not a sensible concept for polynomials over fields. ... definitions of primitive polynomials over finite fields. ... as meaning a polynomial whose roots generate the multiplicative group ...
    (sci.math)
  • Re: Primitive polynomial over/of GF(p^m)
    ... means the coefficients of the polynomial is from GFwhere p denotes ... The primitive polynomial used to create the extension field, ... Primitive polynomials in the specific field that you are working ...
    (comp.dsp)
  • Re: Primitive polynomial over/of GF(p^m)
    ... means the coefficients of the polynomial is from GFwhere p denotes ... The primitive polynomial used to create the extension field, ... Primitive polynomials in the specific field that you are working ...
    (comp.dsp)