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, x2 etc.

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

The software is released under the GNU General Public License.

The following are defined in ff_2_xxx.h:

type ff_blocktype of a block
struct ff_element_structa struct for field elements
type ff_elementa field element (a one element array of ff_element_struct's)
macro FFBITSbit-length of field elements
macro BLOCKSnumber of blocks in an element
ff_element ff_onethe unity ff_element
ff_element ff_zerothe 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.