multiplying polynomials in GF(2) [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or开发者_如何学JAVA rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 10 years ago.

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

---

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.

---

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.

---

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!