---

download - write to the author

Binary finite field library 0.02

This C library implements the basic arithmetic functions for binary finite fields, namely addition, squaring, multiplication, inversion and division. For the sake of completeness we also have subtraction, although it is just the same as addition for binary fields.

A binary finite field is the quotient of the ring of polynomials with binary coefficients modulo the ideal generated by an irreducible polynomial f(x). This software uses the polynomial representation for field elements. Namely, any element is stored in a structure containing an array of blocks which represent the binary coefficients for the polynomial starting from the coefficients of 1, x, x² etc.

The library can be downloaded as a tar archive, containing:

• A header file ff_2_xxx.h where xxx is the bit-length of field elements (equivalently the degree of the generating polynomial)
• The source file ff_2_xxx.c
• A test program ff_test.c
• A benchmark program ff_benchmark.c
• A sample Makefile
• The GPL license version 2

The software is released under the GNU General Public License.

The following are defined in ff_2_xxx.h:

type ff_block	type of a block
struct ff_element_struct	a struct for field elements
type ff_element	a field element (a one element array of ff_element_struct's)
macro FFBITS	bit-length of field elements
macro BLOCKS	number of blocks in an element
ff_element ff_one	the unity ff_element
ff_element ff_zero	the zero ff_element

The following functions are implemented:

Arithmetic functions

void ff_add ( ff_element a, ff_element b, ff_element c )

c <- a + b

void ff_sub ( ff_element a, ff_element b, ff_element c )

macro alias for ff_add

void ff_square ( ff_element a, ff_element b )

b <- a2

void ff_mul_rlcomb ( ff_element a, ff_element b, ff_element c )

c <- a×b using right to left comb algorithm

void ff_mul_lrcomb ( ff_element a, ff_element b, ff_element c )

c <- a×b using left to right comb algorithm

void ff_mul_lrcomb_w4 ( ff_element a, ff_element b, ff_element c )

c <- a×b using base 16 left to right comb algorithm

void ff_mul ( ff_element a, ff_element b, ff_element c )

Presently an alias for ff_mul_lrcomb_w4

void ff_inv ( ff_element a, ff_element b )

b <- 1/a

void ff_div ( ff_element a, ff_element b, ff_element c )

c <- a / b

int ff_eq ( ff_element a, ff_element b )

return 1 if a=b, 0 otherwise

Setting and Input/Output fuctions

void ff_copy ( ff_element a, ff_element b )

b <- a

void ff_set ( ff_element a, ff_block b [BLOCKS] )

Set a from the blocks of b (big-endian)

void ff_rand ( ff_element a )

Randomize a

void ff_read ( ff_element a )

Set a from stdin

void ff_sread ( const char * s, ff_element a )

Set a from string s

void ff_print ( ff_element a )

Print a to stdout

Download

To get the library, fill the following form:

System type. If your system is not included and none of the options works for you, write to antonio@beautylabs.net

x86 32 bits

AMD/64 bits

C type for the basic block (unsigned int is usually the best choice)

unsigned long long int

unsigned long int

unsigned int

unsigned short int

unsigned char

Endian-ness for input-output routines

Big-endian

Little-endian

Finite field (as space-separated degrees)

8 4 3 1 0

163 7 6 3 0

163 8 2 1 0

233 74 0

256 16 3 1 0

283 12 7 5 0

512 51 2 1 0

705 8 7 1 0

Custom:

Notice: the file is in tar format. In case your browser doesn't do it automatically, choose "Save as" and give it a name like ff.tar

If you have comments, suggestions for improvements, have problems in using the library or find it useful, feel free to contact me at the address antonio@beautylabs.net.