Polynomials over Z_2?

[Emmanuel Thomé]

Hi Niels,

gf2x does a bit of that; only multiplication, really, but some neat tricks 
for large multiplies (with a bit of code from Marco). Paul has code for 
more operations, that he used for primitive trinomial search. Gf2x was 
originally written in 2008, but maintenance has been done by me since.

Some code was developed after gf2x, and has incorporated new ideas (albeit 
not by building on top of it).

The folks in Taiwan developed code that implements some more recent FFT 
refinements, and they have data that shows good performance.

Harvey, Lecerf and Van der Hoeven also have nice performing code.

This being said, I'm not convinced that embedding gf2x into gmp would be a 
good idea.

E.

On September 9, 2021 22:59:51 nisse at lysator.liu.se wrote:

> 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 at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-devel