multiplying polynomials in GF(2)

Question

i want to multiply 2 polynomials in gf(2) in c#. please help.

Answer 1

You would probably want to use bitwise operators, and represent the polynomials using the ulong or uint type. That is, if P₆₄(GF(2)) is acceptable. If not, you will have to use some other trick.

ulong a, b;
// Compute r = x * y
ulong r = 0;
for (uint i = 0; i < 64; ++i) {
    if ((a & (1 << i)) != 0) {
        r ^= b << i;
    }
}

A summary of the representation:

• z & (1 << i) selects the xⁱ coefficient from z(x)
• r ^= b << i computes r'(x) = r(x) + b(x)*xⁱ

Disclaimer: I am not a C# programmer.

Answer 2

OK.

• define a class which represents a Galois Field.
• define a class which represents a polynomial over a field.
• define a multiplication operator on polynomials
• and you're done.

Perhaps you can be more explicit about the step where you're having problems.

Answer 3

Wow, that's a big question, which mostly depends on the type of the fields you have to use.

A good introduction is Sage's manual page for finite fields computation.

Executive Summary: For small fields (|F|<2¹⁶) use tables of Zech logs via the Givaro C++ library. For bigger fields use PARI. Fields of characteristic 2 (which is what you need) use NTL.

A paper about implementation of fields is available at ACM, it describes how was it done with Maxima Computer Algebra System.

But if you just need a small toy library to factor polynomials over fields for homework assignment here's what I would do:

1. Create a class which represents a polynomial, it should adds multiply and divides polynomials. A polynomial is easily representable as an array. Make the polynomial class a generic class, like so Polynomial<coefficient_type>.
2. Create a class which represents the group Z_p, for prime p. This class will be the coefficients of the polynomial. Use Z₂ for your fields.
3. Create a class that factors a polynomial.
4. To represent GF(p^k) find an irreducible polynomial of degree k, and all polynomials of degree up to k over Z_p are your elements.
5. Adding them is easy (add coefficients, they are already in Z_p)
6. After multiplying two polynomials, make sure you divide the result modulo the irreducible polynomial chosen in 4.

Thus you'll achieve a generic simple program which can add and multiply elements over all finite fields!