Appendix

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

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;
     }

Appendix

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

Generic Ring Interface