Implementation of Galois field arithmetic

Question

Do you know of an implementation of Galois field arithmetic in C++? At least cases like GF(2¹⁶) and GF(2³²) should be covered. Performance is a concern, so the implementation should have given some thought to optimizing its operations.

I'd prefer a common computational library or a small library dedicated to this task alone. Lacking these, I'd also welcome some readable source code.

Perhaps you can use the code that implements [GCM Mode](http://www.cryptopp.com/wiki/GCM_Mode) in [crypto++](http://www.cryptopp.com/). — jxh, Dec 12 '12 at 06:26
@user315052, please make that comment an answer: [`gcm.cpp`](http://www.cryptopp.com/docs/ref/gcm_8cpp_source.html) does contain some GF2 operations, and its use of SSE2 indicates that performance was considered. Comments are few. I'd like to see this included with the other answers, so that I can use votes as an indication as to how SO users compare this to other suggestions. — MvG, Dec 12 '12 at 07:50

score 8 · Answer 1 · answered Dec 12 '12 at 08:00

I found a link to a Galois Field Arithmetic Library by Arash Partow in the Wikipedia article on Finite field arithmetic.

At first glance, the code looks almost completely without comments, but written in a structured and therefore presumably understandable way. Performance doesn't appear to be an important design criterion, though: use of inlined functions is rather limited, and in general it appears like a direct notation of the theoretic math was deemed more important than expliting computational shortcuts. I list this here for completeness, so that you can have a look, form your own opinion, and can vote or comment accordingly.

score 2 · Accepted Answer · answered Dec 12 '12 at 09:27

2

Perhaps you can use the code that implements GCM Mode in crypto++ (in particular, gcm.cpp). Crypto++ is a free C++ library implementing many crypto schemes. Among them is GCM which uses Galois Field arithmetic.

According to the license, the library itself is copyrighted, while the individual source files are public domain.

answered Dec 12 '12 at 09:27

jxh

69,070
8
110
193

I just learned that a [machine instructions for carry-less multiplication](https://en.wikipedia.org/wiki/CLMUL_instruction_set) (called `PCLMULQDQ` and friends) can be used to perform Galois field multiplication a lot more efficient than other methods. I also saw that crypto++ is among those libraries which support that instruction. – MvG Apr 26 '14 at 21:53

score 0 · Answer 3 · answered Dec 12 '12 at 07:05

0

There's a library called NTL: http://www.shoup.net/ntl/ . Though its source code ain't quite "readable".

answered Dec 12 '12 at 07:05

Joker_vD

3,715
1
28
42

The [GF2E](http://www.shoup.net/ntl/doc/GF2E.txt) module should implement GF(2^e) for arbitrary e. However, it appears to work for arbitrary degree polynomials, so it is likely based on GMP instead of simple machine integers for polynomials with 16 or 32 coefficients. If so (still need to verify this), then this seems like a waste of resources, both memory and cpu. – MvG Dec 12 '12 at 08:10

score 0 · Answer 4 · edited May 23 '17 at 12:32

0

Looking for algebraic numbers, I stumbled upon this answer which suggests Givaro. And looking at that, I found that it does GF(p^k) arithmetic as well. The documentation is thin, but the sources show quite a bit of code and effort. Haven't dug into details yet, but I thought I'd include it in my list here.

edited May 23 '17 at 12:32

Community

1
1

answered May 28 '13 at 10:12

MvG

57,380
22
148
276

Implementation of Galois field arithmetic

4 Answers4