How to represent a binary field in programming language?

Question

I am working on my project of Elliptic Curve Cryptography which requires programming on binary fields. It includes basic operations like addition, multiplication, inversion etc w.r.t. an irreducible binary polynomial.

I am searching for a way by which these binary polynomials can be stored in a program. I am working on C and C++ programming language (with gmp library) so the first thought came to my mind was to use structures and bit-fields. But they are not dynamic and can't hold arbitrarily long polynomials. Using C++ Vector STL is possible but it won't be efficient, as it stores a single bit in a single word of 8 or more bits.

Is there any way of representation which is efficient?

Emmyemmye

By "binary field" do you mean Z_2? – Perusal

std::vector<bool> use 1 bit memory for 1 bit representation – Sultry

@Sultry yes but you can't e.g. efficiently xor two std::vector<bool>s. – Perusal

Your best bet is probably boost::dynamic_bitset. – Perusal

Why the down votes? Isn't this a perfectly reasonable question? Stackoverflow seems to become less and less useful ... – Centesimo

@n.m. Yes you are are right. Actually I am using binary field of order m. Boost library and vector<bool> seem good to me till now. – Emmyemmye

Please pick one langauge, you can't program in two different languages at once.C or C++ will give different answers. – Nicol

@Centesimo Probably everyone is sick and tired of all newbies asking questions about the "C/C++ language". (I didn't down vote) – Nicol

@Nicol : Removed the C tag. – Emmyemmye

@Lundin: But he does use both languages! gmp is a C library and his application seems to be in C++. [edit: removed snark] – Centesimo

I assume both the polynomial coefficients and the values (of x, x^2, x3 etc) are binary (normal definition of binary field in abstract algebra). Then some C or C++ bignum library should be a fast way of achieving what you want. – Scrummage

Ah OK didn't know the term. More used to "characteristic 2 field". – Perusal

Then you probably don't want bit vectors or bitsets, but either plain unsigned integers or bignums mod 2^n. – Perusal

Answer 1

It is NOT effectiv to store informations bitwise in an array. If I were you I would store the Bit-Informations in a big UNSIGNED LONG INTEGER and write a function that can get and put the bits in and out of this cluster of integer value. This way of storing the bit-information would speed up your solution up to 64 times!

Kola

You are right. But that won't be dynamic and restrict data size to just 64 bits. – Emmyemmye

Use a dynamic array of integers as underlying storage. The access function would cover this. The add/remove functions would grow and shrink the array using realloc(). @Emmyemmye – Recursion

@Emmyemmye - It's my understanding that the irreducible binary polynomial is fixed in size, and it's only the data that is variable length, and assuming this is true, then most of the time you're working with fixed length variables, which could be arrays of 32 or 64 bit unsigned integers. – Hokum