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