Polynomials over Z_2?

[Niels Möller]

Hi,

a friend of mine has been hacking a python module for arithmetic over
Z_2 (https://github.com/enok71/gint). And that got me to wonder if this
kind of arithmetic would make sense as an addition to gmp? We could
reuse mpn and mpz data representation (just ignoring mpz sign, since -1
= 1), and add a few new functions that interpret the bits as polynomial
coefficients (where the existing xor functions correspond to polynomial
addition). Interesting operations would be multiplication, euclidean
division, gcd and modular inverse, and modular exponentiation.

To me it seems a bit tricky to do polynomial mul (aka carryless mul)
efficient in plain C, so there's use for some cleverness. And some archs
have special instructions for it, mainly motivated by GCM performance, I
think. And the slower base case is, the lower the Karatsuba threshold
would be.

One curious detail is that squaring seems to be O(n), since in
characteristic 2, f(x)^2 = f(x^2) (all the O(n^2) cross terms cancel),
so as a bit operation, squaring just replaces 0 with 00 and 1 with 01.
Maybe that could be exploited in some way to make a^2 mod b, and hence
modular exponentiation, more efficient.

It's unclear to me what applications there are for arithmetic on *large*
polynomials over Z_2, though. The applications I'm aware of, in crypto
and coding, all use a modulo polynomial of quite modest size, to
representing GF(2^n) for n at most a few hundred.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.