ZEN

A toolbox for fast computation in finite extension over finite rings

Acknowledgements

Authors

Links

PIPS

documentation

example

license

sourceforge

sources

zen

zenfact

ZEN example

Representations of GF(2ⁿ)

An example using ZEN library
This example is extracted and translated from [1].

Principle

Mathematically the finite field GF(2ⁿ) is unique: two field structures with 2ⁿ elements are isomorphics. However, all these representations are not equivalent algorithmically. Here are some examples:

Let P(X) be an irreducible polynomial over GF(2) of degree n, the polynomial extension ^GF(2)[X]/_P(X) is a representation of GF(2ⁿ). One can note that every irreducible polynomial of degree n induces a different representation. In order to improve arithmetic performances, a sparse polynomial is often used.
A natural idea is to use extensions towers when n isn't prime. For instance, one can represent GF(2¹⁰²⁴) as the double extension (^GF(2)[X]/_P(X))[Y]/_Q(Y), where deg(P) deg(Q) = 1024. According to [2], this method can improve computations.
One can also use normal basis for representing a finite field.

Implementation

Efficiency test

We use the multiplication of two elements as an indicator of the efficiency of the representation. Our test function is written once for all representations, as follows:

void TestMultiplication(R)
     ZENRing R;
{
  ZENElt A[NBTESTS],B[NBTESTS];
  int i;
  double tt;
  
  for(i=0;i < NBTESTS;i++)
    {
      ZENEltAlloc(A[i],R);
      ZENEltSetRandom(A[i],R);
      ZENEltAlloc(B[i],R);
      ZENEltSetRandom(B[i],R);
    }

  tt=runtime();
  for(i=0;i < NBTESTS;i++)
    ZENEltMultiply(A[i],B[i],A[i],R);
  tt=runtime()-tt;
  printf("%d tests done: %f ms CPU/test\n",i,tt/i);
	 
  for(i=0;i < NBTESTS;i++)
    {
      ZENEltFree(A[i],R);
      ZENEltFree(B[i],R);
    }
}

The ZEN function runtime is used to measure computation times. In order to measure exactly the multiplication times, we use element arrays that are allocated and defined before.

Extension representations

Simple extension

We now build our representations, and first GF(2).

  BigNumDigit q=2;
  ZENBaseRingAlloc(R,&q,1);

We now choose an irreducible polynomial of degree DEG

  ZENPolyAlloc(P,DEG,R);
  ZENPolySetRandomIrreducible(P,DEG,R);
  printf("P(X)="); ZENPolyPrintToFile(stdout,P,10,R); printf("\n");

We now build the extension ^GF(2)[X]/_P(X) and we bench this first representation.

  ZENExtRingAlloc(E,P,R);
  TestMultiplication(E);

The arithmetic operations could be improved by using some precomputations. We activate the ZEN implemented precomputations, first on GF(2);

  ZENPrcSetNone(prc);
  ZENPrcSet(prc,ZENPRC_ELT_MULTIPLY);
  ZENRingAddPrc(R,prc);
  TestMultiplication(E);

Then, we do the same on the extension:

  ZENRingAddPrc(E,prc);
  TestMultiplication(E);

We can now test the influence of the polynomial choice. We now use a polynomial of the form P(X)=X^DEG+f(X) with f a polynomial of small degree, and redefine our extension.

  ZENPolySetGoodIrreducible(P,DEG,R);
  ZENExtRingAlloc(E,P,R);
  printf("P(X)="); ZENPolyPrintToFile(stdout,P,10,R); printf("\n");
  TestMultiplication(E);

Double extension

Let's see how we build the double extension alternative (^GF(2)[X]/_P(X))[Y]/_Q(Y). We first define an irreducible polynomial of degree EXT of the more efficient form P(X)=X^EXT+g(X)

  ZENPolySetSmallestIrreducible(P,EXT,R);
  ZENExtRingAlloc(E1,P,R);

We now try to find another irreducible polynomial over GF(2^EXT) of degree DEG/EXT and we build the second extension:

  ZENPolyAlloc(P2,DEG/EXT,E1);
  ZENPolySetRandomIrreducible(P2,DEG/EXT,E1);
  poly2=ZENPolyPrintToString(P2,10,E1);
  printf("P2(X)= %s\n",poly2);

  ZENExtRingAlloc(E2,P2,E1);
  TestMultiplication(E2);

However, if the degree EXT of the first extension is small enough, tabulations can be performed for the arithmetic operations of this field. This can be made through the cloning concept in ZEN.

 ZENClnSetAll(cln);
 C1=ZENRingClone(E1,cln);

As cloning modifies the element representation, we must rebuild the second extension using the memorized polynomial. This memorization is done using a string representation.

 ZENPolyReadFromString(P2,poly2,10,C1);
 ZENExtRingAlloc(EC2,P2,C1);
 TestMultiplication(EC2);

We can also add some more precomputations to this new representation:

 ZENRingAddPrc(C1,prc);
 TestMultiplication(EC2);

 ZENRingAddPrc(EC2,prc);
 TestMultiplication(EC2);

Experiments

We have tested this program in GF(2¹⁰²⁴) case on a Sparc 10 running at 50 MHz. The results are given in figure 1, where the following mentions are used:

P indicates that precomputations have been done for the corresponding ZENRing.
S indicates that a suited polynomial has been used.
C indicates that a clone of the ring has been built.

The precomputations time don't take in account the determination of the irreducible polynomials.

simple extension	GF(2)	GF(2¹⁰²⁴)	precomputations (s)	multiplication (ms)
	-	-	0.01	5.0
	P	-	0.01	5.0
	P	P	0.13	5.0
	P	S	0.01	3.2
	P	SP	0.20	3.0

double extension	GF(2⁸)	GF(2¹⁰²⁴)
	S	-	0.01	300
	C	-	5.8	19
	CP	-	5.8	19
	CP	P	1200	19
	S	S	0.01	67
	CP	S	5.8	10
	CP	SP	82	10

double extension	GF(2¹⁶)	GF(2¹⁰²⁴)
	S	-	0.00	88
	C	-	38	11
	CP	-	38	11
	CP	P	38	11
	S	S	0.00	27
	CP	S	38	5.5
	CP	SP	38	5.5

Fig. 1: Efficiency of various representations of GF(2¹⁰²⁴)

Simple extension

Our reference will be the standard representation using a random irreducible polynomial of degree 1024. The initialization time is non significant in this case. The multiplication of two elements takes about 5 ms and precomputations are unuseful. On te contrary, the use of the peculiar polynomial form P(X)=X^DEG+f(X) makes a significant improvement of 35%. In this case precomputations achieves a global improvement of 40%.

Double extension

First extension of degree 8

If the first extension is of degree 8, then all the operations can be tabulated. Without the tabulation, the result is awful (300 ms), because this representation is very expensive for the memory. On the contrary, after tabulation the elements of the first extension are coded on 8 bits, which is more efficient. The improvement in this case is a 15 gain factor ! A good choice of the polynomial is again worthwhile.

First extension of degree 16

With this new representation, the initial performance is a little better than with the extension of degree 8 (88 ms). The cloning operation is much slower (38 s compared to 6 s), but this results in multiplicative operations in 11 ms. Using a specific representation for the polynomials gives almost the same result as in the simple extension case before optimization. Contrary to some other results (see [2]), we hence observe no amelioration using a double extension. This is certainly due to the fact that using ZEN, some tabulations are performed in the simple extension case. However, this result depends a lot on the computer, architecture, and optimization options. For instance, the example given in the postscript documentation of zenfact shows that on PCs under linux, the double extension may improve the performance. The good point is that using ZEN, one can test all those representations on one's program at no cost : it's just a matter of defining the ring.

References

[1] F. Chabaud.
Recherche de performance dans l'algorithmique des corps finis. Applications à la cryptographie.,
Thèse de doctorat, École Polytechnique, Oct. 1996.
[2] E. De Win, A. Bosselaers, S. Vandenberghe, P. De Gersem and J. Vandewalle.
A fast software implementation for arithmetic operations in GF(2ⁿ),
ASIACRYPT'96, LNCS 1163, pages 65-76, 1996.

Acknowledgements

Authors

Links

PIPS

documentation

example

license

sourceforge

sources

zen

zenfact

Florent Chabaud
E-mail: florent.chabaud@m4x.org
GPG key:

ZEN

Representations of GF(2n)

Principle

Implementation

Efficiency test

Extension representations

Simple extension

Double extension

Experiments

Simple extension

Double extension

First extension of degree 8

First extension of degree 16

References

Representations of GF(2ⁿ)