[Libre-soc-bugs] [Bug 782] add galois field bitmanip instructions

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=782

--- Comment #46 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #44)
> (In reply to Jacob Lifshay from comment #43)
> > (In reply to Luke Kenneth Casson Leighton from comment #42)
> > > (In reply to Jacob Lifshay from comment #41)
> > > > though, do we really need gfdiv? 
> > > 
> > > i'm sure i've seen modulo (remainder) used somewhere.
> > 
> > yes, in defining gf(2^n) in terms of gf(2) polynomials, the polynomial
> > remainder is used. that is *not* a gfbrem.
> 
> bear in mind, i don't understand the difference, so i am trusting you to
> ask and answer this question: why then have several people published
> divmodGF2 algorithms in their GF2 libraries?

think of it like this:

class GFp:
    """Galois Field GF(p) with the number of elements that is a prime `p`.
        these are isomorphic to the integers mod `p`, though it can be defined
differently
        (e.g. by using `GFPrimeToTheK` with `k == 1`).
    """
    def __init__(self, p, v=None):
        if v is None:
            v = 0
        self.v = v % p
        self.p = p

    ...
    # no % or divmod here, since % would always return 0

class Polynomial(Generic[T]):
    """A polynomial with coefficients of type T.

        `coefficients[i]` is the coefficient for `x ** i`
    """
    def __init__(self, coefficients=()):
        self.coefficients = list(coefficients)
    ...
    def __divmod__(self, rhs):
        """Polynomial divmod makes sense for all polynomials, even if it
doesn't make
            sense to divmod a coefficient.
        """
        ...
    @property
    def degree(self):
        retval = 0
        for i, c in enumerate(self.coefficients):
            if c != 0:
                retval = i
        return retval

class GFpPolynomial(Polynomial[GFp]):
    """Polynomial with coefficients that are GFp with matching p"""
    def __init__(self, coefficients, p):
        super().__init__(coefficients)
        self.p = p
        for i in self.coefficients:
            assert isinstance(i, GFp)
            assert i.p == p

class GFPrimeToTheK:
    """aka. GF(q) where q = p ** k. Galois Field with number of elements
        that is a prime `p` raised to the power `k` where `k`
        is a positive integer. This isn't a polynomial (though mathematicians
        kinda mix their abstraction layers together whenever convenient),
        but is usually defined as the polynomial remainders you get from
        dividing `GFpPolynomial`s by a specific reducing `GFpPolynomial`
        `reducing_polynomial` of degree k.
        `p`, `k`, and the `reducing_polynomial` define a specific Galois Field,
        with the addition of the remainder polynomial, you get a specific
        Galois Field element.
        Note that the general shape of a Galois Field doesn't depend on what
        specific reducing polynomial you've selected (they are all isomorphic
        to each other for a specific `p` and `k`), so when people don't care,
        they just leave the reducing polynomial unstated and up to the reader
        to pick.
    """
    def __init__(self, p, k, reducing_polynomial, remainder):
        self.p = p
        self.k = k
        self.reducing_polynomial = reducing_polynomial
        assert isinstance(reducing_polynomial, GFpPolynomial)
        assert isinstance(remainder, GFpPolynomial)
        assert p == reducing_polynomial.p
        assert k == reducing_polynomial.degree
        assert reducing_polynomial.is_irreducable()
        self.remainder = remainder % reducing_polynomial

    ...
    # no % or divmod here, since % would always return 0
> 
> they must be used for something.

well, the top result in google for divmod "gf2" for me is:
(changed to link to source code, yes i tried -- https doesn't seem to work)
http://www.diegm.uniud.it/~bernardi/Software/Cplusplus/galoislib_doc/gf2_8H-source.html#l00201

00201   void divmod(GF<FieldSize> a, GF<FieldSize> &quot, GF<FieldSize> &rem)
00202   {
00203     quot = a*inv(*this);
00204     rem  = GF<FieldSize>::zero();
00205   }

As you can see, the remainder is always zero.

I'd guess divmod is used here for API compatibility with Rings, where a
remainder is actually useful, such as the Ring of integers.

-- 
You are receiving this mail because:
You are on the CC list for the bug.