5. Effective computation of

The usual way to compute Zech's logarithms is exposed in [7]. Let $\mathrm{GF}\! \left( q \right)$ be represented as $\left. \left( \mathbb {Z}\! \left/ p\right. \left[ X\right] \right) \right/ P_{\xi }$ for some primitive $P_{\xi }$ . The successive powers of $\xi$ are tabulated in the vector space $\left( \mathbb {Z}\! \left/ p\right. \right) ^{m}$ , the reciprocal mapping being tabulated by the way.

Then, calculating : $Z_{\xi }\left( s\right) =L_{\xi }\left( 1+L_{\xi }^{-1}\left( s\right) \right)$ is very easy since, in the vector space representation, adding 1 is going forwards to the next element, or going $p-1$ places backwards.

The cost of that method is quite equal to $q=p^{m}$ reductions $\,{\rm mod}\,P_{\xi }$ of polynomials and each of them costs $\mathrm{O}\left( m \right)$ operations in $\mathbb {Z}\! \left/ p\right.$ .

5.2 Finding irreducible or primitive polynomials

There are exactly $q$ monic polynomials of degree $m$ over $\mathbb {Z}\! \left/ p\right.$ , but a lot of them are composite. Each irreducible polynomial among them characterizes a whole-sized $\psi$ -orbit in $\mathrm{GF}\! \left( q \right)$ . Thus the number $\char93 \mathrm{imp}\left( q \right)$ of such polynomials is the number of proper elements of $\mathrm{GF}\! \left( q \right)$ divided by $m$ .

That number can be expressed in terms of the Moebius function, defined as $\mu \left( x\right) =0$ when $x$ is not square-free and, otherwise, as $\mu \left( x\right) =\pm 1$ according to the parity of the number of primes dividing x. Thus

$\begin{displaymath} \char93 \mathrm{imp}\left( q \right) =\frac{1}{m}\sum _{d\vert m}p^{d}\, \mu \left( \frac{m}{d}\right) \end{displaymath}$

(6)

Roughly speaking, one polynomial over $m$ is irreducible, enabling a probabilistic search for that kind of polynomials. The irreducibleness of $P\in \left( \mathbb {Z}\! \left/ p\right. \right) _{m}\left[ X\right]$ can be tested by checking if $P$ is relatively prime to the Fermat characteristic polynomials of any strictly embedded field, i.e. by calculation of $\gcd \left( P\left( X\right) ,\, X^{2\: \widehat{\: }\, d-1}-1\right)$ , where $d$ ranges over maximal divisors of $m$ . And before the usual Euclid's algorithm, the characteristic polynomial can be evaluated mod $P$ at a cost remaining polynomial in $m$ .

On the other hand, if $x$ is primitive in $\mathrm{GF}\! \left( q \right)$ , so are its $\psi$ -conjugates, and therefore the number $\char93 \mathrm{pmp}\left( q \right)$ of primitive (monic) polynomials of degree $m$ over $\mathbb {Z}\! \left/ p\right.$ is given by :

And then again a probabilistic search can be undertaken. Its semantic is checking if $P$ is a factor of the cyclotomic $\Phi _{q-1}$ , that can be done by checking if $P\in \left( \mathbb {Z}\! \left/ p\right. \right) _{m}\left[ X\right]$ is relatively prime to the $X^{d}-1$ , where $d$ ranges over the maximal divisors of $q-1$ , tests that remain polynomial in $m$ .

5.3 Admissible exponents

Let us now define an admissible exponent for $\mathrm{GF}\! \left( q \right)$ as an element $a\in \mathbb {N}_{q}$ such that it exists some primitive element $\alpha \in \mathrm{GF}\! \left( q \right)$ verifying $\alpha ^{a}=1+a$ . Obviously, $m\leq a\leq q-m$ . Moreover, if $a$ is admissible, so is $b=q-a$ too, being relative to $\beta =\alpha ^{-1}$ since $0=\beta ^{-a}-\beta ^{-1}-1=\beta ^{q-a}-\beta ^{q-1}-\beta ^{q}$ implies $\beta ^{b}-1-\beta =0$ .

The exponent $a$ being the same for all members of a $\psi$ -orbit of primitives, the number of such exponents is at most $\char93 \mathrm{pmp}\left( q \right)$ . And that bound seems to be tight, since, for $p=2$ and small $m$ , there are very few, if any, $\psi$ -orbits of primitives belonging to the same exponent, as illustrated in Table 3.

Table 3: Admissible exponents for small values of $m$ .

$m$	$q$	$\char93 \mathrm{pmp}\left( q \right)$	$nb\_adm$	$m$	$q$	$\char93 \mathrm{pmp}\left( q \right)$	$nb\_adm$
$4$	$16$	$2$	$2$	$12$	$4096$	$144$	$140$
$5$	$32$	$6$	$6$	$13$	$8192$	$630$	$630$
$6$	$64$	$6$	$6$	$14$	$16384$	$756$	$732$
$7$	$128$	$18$	$18$	$15$	$32768$	$1800$	$1736$
$8$	$256$	$16$	$16$	$16$	$65536$	$2048$	$2006$
$9$	$512$	$48$	$48$	$17$	$131072$	$7710$	$7464$
$10$	$1024$	$60$	$58$	$18$	$262144$	$7776$	$7618$
$11$	$2048$	$176$	$176$

5.4 Rebuilding from an admissible exponent

In that paragraph, the former knowledge of an admissible exponent $a$ is assumed, i.e. the existence of a $\xi \in \mathrm{GF}\! \left( q \right)$ such that $\xi +1=\xi ^{a}$ . Then computing the $Z_{\xi }$ function over $CO\left( 1\right)$ , the coset orbit of $1$ , is straightforward with formulae (4) and (5), i.e. with

$\begin{displaymath} Z\left( 2s\right) =2Z\left( s\right) \quad ;\quad Z\left( -s... ...( s\right) -s\quad ;\quad Z\left( Z\left( s\right) \right) )=s \end{displaymath}$

(8)

But only (at most) $6m$ elements are reached at that step, and «jumping» to other coset orbits is required. Such jumps are based on :

which is a simple application of definitions. On the left, we have : $\xi \; \: \widehat{\: }\, \left( Z\left( Z\left( s+k\right) -k\right) \right)... ...\, \left( Z\left( s+k\right) -k\right) =1+\xi ^{-k}\left( 1+\xi ^{s+k}\right)$ , and on the other one : $\xi \; \: \widehat{\: }\, \left( Z\left( Z\left( s\right) +k\right) -k\right)... ...idehat{\: }\, \left( Z\left( s\right) +k\right) \right) =\xi ^{-k}+1+\xi ^{s}$ .

That «jump formula» yields to following algorithm : start from an $s\in \mathbb {N}_{q}$ having a known $Z\left( s\right)$ ; seek for a $k\in \mathbb {N}_{q}$ such that $Z\left( s+k\right)$ and $Z\left( Z\left( s\right) +k\right)$ are also known (i.e. former reached in building process) and define :

$\begin{displaymath} t\doteq Z\left( s+k\right) -k\quad ;\quad \tau \doteq Z\left( Z\left( s\right) +k\right) -k \end{displaymath}$

(10)

If the result $Z\left( t\right) =\tau$ was not previously tabulated, it can be taken as start point for reaching a new coset orbit. Such an algorithm is, in fact, a probabilistic one, since the followed path depends on the seek algorithm, and there is no reason to follows the $\mathbb {N}$ natural order while checking the $k$ 's.

On the contrary, a random seek will ensure a better bargain between «never visited» and «soon visited, but may be changed» items. It is well-known that such a random seek will only double (on the average) the duration of a time-independent search. The counterpart for this (potential) slow-down factor is an ability for concurrent programming and a better reliability [11].

5.5 A probabilistic method

Now, no more previous knowledge about $\mathrm{GF}\! \left( 2^{m} \right)$ is assumed. A value is chosen for $a$ , ranging over $\left[ m\dots q-m\right]$ , and the preceding algorithm is applied. Three results can happen :

Assume normal termination, and denote by $T$ the function tabulated during the course of the algorithm, completed by $T\left( 0\right) =\infty$ and $T\left( \infty \right) =0$ . Then, by construction, $T$ is a bijection $\mathbb {N}_{q}\hookrightarrow \mathbb {N}_{q}$ . Define $\mathbb {A}$ (the first law) by $\infty \mathbb {A}x=x\mathbb {A}\infty =x$ , $x\mathbb {A}x=\infty$ and, otherwise, $x\mathbb {A}y=x+T\left( y-x\right)$ where `` $+$ '' and `` $-$ '' are the usual operations in $\mathbb {Z}\! \left/ q-1\right.$ . Define $\otimes$ (the second law) by $\infty \otimes x=x\otimes \infty =\infty$ and, otherwise, $x\otimes y=x+y$ where again `` $+$ '' is the usual addition in $\mathbb {Z}\! \left/ q-1\right.$ .

We have to prove that $\left( \mathbb {N}_{q},\, \mathbb {A},\, \otimes \right)$ is a field for these laws. Clearly, $\left( \mathbb {N}_{q}\setminus \infty ,\, \otimes \right)$ is a commutative group. To see the distributivity of $\otimes$ over $\mathbb {A}$ , i.e. $x\otimes \left( y\mathbb {A}z\right) =\left( x\otimes y\right) \mathbb {A}\left( x\otimes z\right)$ three cases are to be considered. If $y=z$ , then $x\otimes \left( y\mathbb {A}z\right) =x\otimes \infty =\infty$ and $\left( x\otimes y\right) \mathbb {A}\left( x\otimes y\right) =\infty$ . If $y=\infty$ (or $z=\infty$ ) then $x\otimes \left( y\mathbb {A}z\right) =x\otimes z$ and $\left( x\otimes y\right) \mathbb {A}\left( x\otimes z\right) =\infty \mathbb {A}\left( x\otimes z\right) =x\otimes z$ . Otherwise, we have $x\otimes \left( y\mathbb {A}z\right) =x+\left( y+T\left( z-y\right) \right) =... ...\right) \right) =\left( x\otimes y\right) \mathbb {A}\left( x\otimes z\right)$ .

Commutativity of $\mathbb {A}$ yields from the rules (8) used to build $T$ : $\forall s\in \mathbb {Z}\! \left/ q-1\right. \, :\, T\left( s\right) =T\left( -s\right) +s$ leading to $x\mathbb {A}y=x+T\left( y-x\right) =x+T\left( x-y\right) +\left( y-x\right) =y\mathbb {A}x$ . Therefore, all the properties required for $\mathbb {N}_{q}$ to be a field, with cardinal $q$ , i.e. to be an isomorphic copy of $\mathrm{GF}\! \left( q \right)$ , are fulfilled, except perhaps the associativity of $\mathbb {A}$ when $x,\, y,\, z$ are different from $\infty$ .

But, the definitions and the «jump rule» (9) where $s=z-x$ and $k=x-y$ are leading to

$\begin{eqnarray*} x\mathbb {A}\left( y\mathbb {A}z\right) =x+T\left( y\mathbb {A... ...right) +x-y\right) -x+y=y\mathbb {A}\left( x\mathbb {A}z\right) \end{eqnarray*}$

5. Effective computation of $Z$

5.1 Straightforward calculation for Zech's tables

5.2 Finding irreducible or primitive polynomials

5.3 Admissible exponents

5.4 Rebuilding from an admissible exponent

5.5 A probabilistic method