ZEN example
Representations of GF(2^{n})
An example using
ZEN
library
This example is extracted and translated from [1].
Principle
Mathematically the finite field GF(2^{n}) is unique: two field structures with 2^{n} 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^{n}). 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^{1024}) 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^{1024}) 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^{1024}) 
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^{8}) 
GF(2^{1024}) 



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^{16}) 
GF(2^{1024}) 



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^{1024})
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^{n}),
ASIACRYPT'96, LNCS 1163, pages 6576, 1996.
