I created a misimpression in my note about multiplying GF2 polynomials. I juxtaposed the background of Triangles and Quarter-Squares with my comments about "six different ways to do GF2 polynomial products". I'm in agreement with Joerg: I don't know of a "square to multiply" method for GF2 polynomials, although I haven't concluded it's impossible. The F() function is the closest thing I've seen. The "six different ways" I had in mind are a potpourri of fairly well known techniques: Karatsuba-Ofman & Strassen-Schonhage & FFT, subfields, a couple of variations on Chinese remainder, log/exp tables, and the ever popular "schoolbook" method. The last, which simply calculates all the partial bit products and accumulates them, has myriad variations which are all mathematically equivalent, but the programming varies in a lot of ways, with significant performance differences (and machine dependencies.) One of the more obscure methods is to spread out the GF2 bits in a larger word and use the regular integer or floating point multiplication, and mask off the non-GF2 "noise" in the answer. Another way to represent polynomials is by giving the values at enough points. To multiply them, extrapolate/interpolate to get more values, then multiply the corresponding values. One could write a book, or perhaps a thesis, on the subject. I would be completely unsurprised if the F() method appears in the Bell System Technical Journal in 1955. Rich -----Original Message----- From: Joerg Arndt Sent: Thu 6/29/2006 9:46 AM To: math-fun Subject: Re: [math-fun] New? multiplicaiton of GF2 polynomials rcs> [clip]
I'm looking for an appropriate generalization for GF2 polynomial multiplication. (Multiplication of polynomials where the coefficients are reduced mod 2.) Each of the methods above uses division by 2, so some minor variation is necessary. There are about six different ways to do GF2 polynomial products. I'm wondering if the scheme below is new.
I thought "square to multiply" is impossible for GF2 polynomials... Could you give >=1 example of any such technique? [clip]