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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
