Main Page   Modules   Class Hierarchy   Compound List   File List   Compound Members   Related Pages

## Coding elements GF(p^q)for I/O

As well known, (and if you do not know this, you need to learn about it, otherwise you will not understand what follows) finite field can be implemented by the set of polynomials whose coefficients belong to , the set of integers modulo , and where the polynomial sum and product are taken modulo a suitable polynomial of degree .

This implies that any element of can be though as a polynomial with coefficients in and degree less than . Representing such a polynomial inside the computer poses no problem, however the polynomial representation is not the most convenient for I/O purposes.

Because of this we decide to associate to the element of represented by polynomial

the integer

which can be thought as polynomial formally evaluated at . It is easy to see that, since for every , this is a bijective map between the elements of and the positive integeres less than .

## Generic Ring Interface

The Generic Ring Interface (GRI) is a minimum set of methods that a class implementing a ring must offer.

Before you get too afraid, let me assure you that you do not have to be an expert of rings in order to use this library; this section is included here only for the sake of completeness.

Having formalized the interface of a generic ring allows onw to write template procedures which works for generic rings. For example, an efficient power function which exploits the GRI could be written as follows

```     // The following function computes x**exponent with at
// most 2*log_2(exponent) products.  The algorithm is similar to
// the one used for efficient integer multiplication.
template<class Ring>
Ring pow(Ring x, int exponent)
{
// Initialize the result to the "1" of the ring.
Ring result=Ring::one();

// If the exponent is negative, compute inv(x)**(-exponent)
// Note that inv() raises a RingEx::NonUnitDivision if x
// is not a ring unit (i.e., inv(x) does not exists)
if (exponent < 0)
{
x = inv(x);
e = -e;
}

// Let R be the desired result.  When the code control
// reachs this point, the following equality (trivially) holds
//
//            R = result * (x**exponent)             (+)
while(exponent > 0)
{
// If exponent=2*k+1, we can write
//
//     R = result * (x**exponent)
//       = result * (x * (x*x)**k)
//       = (result * x) * (x*x)**k
//
// while, if exponent=2*k we can write
//
//     R = result * (x*x)**k
//
// Therefore, if exponent is even, we replace x with
// its square x*x and exponent with exponent/2, while
// if exponent is odd, we multiply result by x before
// computing x*x and exponent/2.

if (exponent & 1)    // If exponent is odd, replace
result = result*x; // result with result*x

exponent = exponent >> 1;  // Compute exponent/2
x = x*x;                   // Square x

// In this point equality (+) still holds
}

// Also in this point equality (+) holds, but since exponent is
// zero, then R=result
return result;
}```

The methods that a class Ring must have in order to implement the GRI are

1. Methods that must be implemented by every Ring
• Constructors
• `Ring(int)` For every Ring there is an homomorphism which maps integer into where is the "one" of Ring and the sum is repeated times. This constructor actually implements such an homomorphism, i.e., `Ring(n)` is . Note that `Ring(0)` and `Ring(1)` are the neutral elements of, respectively, the ring sum and product. Such elements are also returned by constructors Ring::zero() and Ring::one() (which, depending on the specific implementation, can be more efficient)
• `Ring()` Default constructor. It must returns `Ring(0)`
• `Ring::zero()` Returns the ring "zero", i.e., the neutral element of the sum
• `Ring::one()` Returns the ring "one", i.e., the neutral element of the product
• Operations
• `binary operators +`, `-`, `*` and their assignament versions (e.g. `+=`), with their obvious meaning
• `unary operators +` and `-` with their obvious meaning
• `inv(x)` If `x` is a unit, `inv(x)` returns the multiplicative inverse, otherwise a `RingEx::NonUnitDivision` exception is thrown
• `binary operator/`. Expression `a/b` is equivalent to `a*inv(b)`, but it could be more efficient.
• `conj(x)` For rings with an involution, returns the conjugated of `x`. If the ring does not have an involution, it should return `x`.
• Boolean methods
• `is_zero()` Returns true if the element is the ring "zero"
• `is_one()` Returns true if the element is the ring "one"
• `is_unit()` Returns true if the element has a multiplicative inverse
• `equality operators ==` and `!=` with their obvious meaning
• I/O
• `I/O operators >> ` and ` << ` to/from ostream/istream's
• Predicates about the ring type
• `is_euclidean()` Return true if the elements belong to an euclidean ring
• `is_normed()` Return true if the elements belong to a normed ring
• `is_field()` Return true if the elements belong to a field
2. Methods required only for euclidean rings
• `deg()` Returns the "degree" of the element
• `divmod(const Ring<T> &b, Ring<T> &quot, Ring<T> &rem)` Method call `x.divmod(y, quot, rem)` returns in `quot` and `rem` the ring elements such that `x=quot*y+rem` and `deg(rem) < deg(x)`.
3. Methods required only for normed rings
• `norm()` Returns the norm of the element.

Generated at Mon Oct 11 14:57:41 2004 for GaloisLib by 1.2.8.1 written by Dimitri van Heesch, © 1997-2001