ALPHABETS PROVIDED BY DEFAULT

OVERVIEW

decoding provides some finite fields and finite rings. However these implementations are not optimized. For efficiency it is strongly recommanded to use external library like GMP or MPFQ. To implement your own finite fields or rings or to wrap external libraries see decoding-rings(3).

DESCRIPTION

The following finite fields and rings are provided by decoding. If the wanted ring is implemented by decoding/rings/wanted_ring.c you must do

#include <decoding/rings/wanted_ring.c>
#include <decoding/algos.c>

to use it. All the proposed rings are in the include/decoding/rings directory. If you do not provide any name for your ring, one will be set by default. It is recommended to use a name with the RING_NAME macro.

#define RING_NAME myring
#include <decoding/rings/wanted_ring.c>
#include <decoding/algos.c>

Every ring in decoding must provide some information like its characteristic or cardinality. Every variable is prefixed by R_ in what follows. To be used in your program the R_ prefix has to be replaced by the ring name, either its default name or the name you gave with the RING_NAME macro. The following must be provided by the ring.

R R_one;

The unity of the ring.

mpz_t R_char;

The characteristic of the ring.

uma R_uma_char;

The characteristic of the ring if it holds within a uma integer. Otherwise R_uma_char is -1.

mpz_t R_card;

The cardinality of the ring if it is finite. If the ring is not finite then R_card is zero.

uma R_ext_degree;

The degree of the ring. If the ring is an algebraic extension, that is A[X] / (f(X)) for a ring A and a polynomial f(X) from Z(A)[X] of degree d then R_ext_degree will be equal to d.

If the ring is a finite field, R_ext_degree will be the degree of the finite field over the prime field.

More variables can be exported by the ring. In that case they will be describe in what follows.

You can of course use several rings in the same program. Suppose you want to use field1.c and field2.c.

#define RING_NAME F1
#include <decoding/rings/field1.c>
#include <decoding/algos.c>

#define RING_NAME F2
#include <decoding/rings/field2.c>
#include <decoding/algos.c>

int main(void) {
  F1 a,b;
  F2 x,y;

  F1_ring_init();
  F2_ring_init();
  F1_inits(a,b,NULL);
  F2_inits(x,y,NULL);

  /* do some stuff with F1 and F2 */
  
  F1_clears(a,b,NULL);
  F2_clears(x,y,NULL); 
  F1_ring_clear();
  F2_ring_clear();
  return 0;
}

In the example above two rings are used and their names (F1 and F2) are given with RING_NAME. Their names are then used to prefixed all the functions involving elements of both rings.

Note that before any use of the fields you must initialize them with the R_ring_init() function. Depending on the ring you want to use the latter function may take arguments. In this case, they are documented in the appropriate sections below.

`GF5.c`

Implements GF(5). It is an example of implementation of a finite field and contains the documentation on the making of finite rings for decoding. See decoding-rings(3) for details. It is not recommended to use this field, if you want to use GF(5) please use the gfp_word.c.

`gf2n_word.c`

Implement all finite fields GF(2^n) with 2 <= n <= 16. Note that it is a poor implementation (prefer MPFQ). It is not intended to be efficient and will most likely never be. Please use the MPFQ wrappers mpfq_gf2n_wrapper.c. If MPFQ is not present on your system then gf2n_word.c will be used instead. You do not have to change your source code as decoding will automatically switch from mpfq_gf2n_wrapper.c to gf2n_word.c.

You can give the extension degree with the EXT_DEGREE macro. It must be an integer in the range [2,16].

#define EXT_DEGREE 8
#include <decoding/rings/gf2n_word.c>
#include <decoding/algos.c>

In the example above, the default name of the ring will be gf2_8.

`gfp_double.c`

Implement all prime fields (Z/pZ) whose characteristic holds within the significand of a double. Be careful, the size of a double and the arithmetic is implementation-defined. NO GUARANTY IS GIVEN ON THE CORRETNESS OF THE ARITHMETIC for gfp_double.c. However it should work just fine on x86 and x86_64 processors. Use PRIME to indicate the prime number defining the finite field.

#define PRIME 101
#include <decoding/rings/gfp_double.c>
#include <decoding/algos.c>

In the example above, the name of the finite field will be gf101.

The prime number defining the field can also be accessed with the R_fp_char variable of type double. Its numerical inverse is stored in the R_fp_char_inv also of type double. For example if PRIME is 101 we have gf101_fp_char == 101.0f and gf101_fp_char_inv == 0.0099009900990098994f.

`gfp_float.c`

Implement all prime fields (Z/pZ) whose characteristic holds within the significand of a float. Be careful, the size of a float and the arithmetic is implementation-defined. NO GUARANTY IS GIVEN ON THE CORRETNESS OF THE ARITHMETIC for gfp_float.c. However it should work just fine on x86 and x86_64 processors. Use PRIME to indicate the prime number defining the finite field.

#define PRIME 101
#include <decoding/rings/gfp_float.c>
#include <decoding/algos.c>

In the example above, the name of the finite field will be gf101.

The prime number defining the field can also be accessed with the R_fp_char variable of type float. Its numerical inverse is stored in the R_fp_char_inv also of type float. For example if PRIME is 101 we have gf101_fp_char == 101.0 and gf101_fp_char_inv == 0.00990098994.

`gfp_gmp.c`

Implement all prime fields (Z/pZ).

#include <decoding/rings/gfp_gmp.c>
#include <decoding/algos.c>

In the example above, the name of the finite field will be gfp_gmp.

void R_ring_init(mpz_t prime);: Initialize the finite field as a prime field of char p. A call to this function is mandatory before doing anything else.
void R_ring_clear(void);: Free the memory occupied by the finite field. A call to this function is recommended when the ring is no more needed.

`gfp_word.c`

Implement all prime fields (Z/pZ) whose char holds within a machine word. Use PRIME to indicate the modulus of the finite field you want to construct.

#define PRIME 101
#include <decoding/rings/gfp_word.c>
#include <decoding/algos.c>

In the example above, the name of the finite field will be gf101. You can use the WORD_TYPE macro to specify which C type to use to represent the elements of the finite field. The given type must be an unsigned type. By default the unsigned int type is used.

#define PRIME 101
#define WORD_TYPE unsigned short
#include <decoding/rings/gfp_word.c>
#include <decoding/algos.c>

`rationals_gmp.c`

Implement the field or rational numbers.

#include <decoding/rings/rationals_gmp.c>
#include <decoding/algos.c>

In the example above, the name of the finite field will be rationals_gmp.

`mpfq_gf2n_wrapper.c`

Implement all fields GF(2^n) with 2 <= s <= 255. It is a wrapper to MPFQ. The EXT_DEGREE indicates which extension of GF(2) you want to use.

#define EXT_DEGREE 8
#include <decoding/rings/mpfq_gf2n_wrapper.c>
#include <decoding/algos.c>

In the example above, the name of the finite field will be gf2_8.

AUTHOR

Written by Guillaume Quintin (quintin@lix.polytechnique.fr).

ALPHABETS PROVIDED BY DEFAULT

OVERVIEW

DESCRIPTION

GF5.c

gf2n_word.c

gfp_double.c

gfp_float.c

gfp_gmp.c

gfp_word.c

rationals_gmp.c

mpfq_gf2n_wrapper.c