6. Efficient exponents

For small values of $m$ , the previously described algorithm can be run for all values ranging over $\left[ m\dots q-m\right]$ , classifying them according to (§5.5) into «efficient», «wrong» and «dubious». Some results are listed in Table 1.

Table 4: Efficient exponents for small values of $m$ .

$m$	$\char93 adm$	$\char93 dub$	$\char93 bad$	$\char93 efficient$	$list$
$4$	$2$	$0$	$6$	$2$	$\left\{ 4,\, 12\right\}$
$5$	$6$	$6$	$10$	$6$	$\left\{ 12,\, 13,\, 14,\, 18,\, 19,\, 20\right\}$
$6$	$6$	$6$	$42$	$4$	$\left\{ 6,\, 25,\, 39,\, 58\right\}$
$7$	$18$	$18$	$78$	$18$	$\left\{ 7,\, 10,\, 14,\, 19,\, 21,\, 31\dots \right\}$
$8$	$16$	$22$	$210$	$8$	$\left\{ 13,\, 25,\, 99,\, 115,\, 141\dots \right\}$
$9$	$48$	$88$	$376$	$30$	$\left\{ 11,\, 36,\, 51,\, 69,\, 71,\, 84\dots \right\}$
$10$	$58$	$434$	$542$	$28$	$\left\{ 57,\, 79,\, 85,\, 103\dots \right\}$
$11$	$176$	$1184$	$764$	$78$	$\left\{ 25,\, 56,\, 69,\, 112,\, 190\dots \right\}$
$12$	$140$	$2650$	$1410$	$12$	$\left\{ 448,\, 601,\, 918,\, 1500,\, 1771,\, 1990\dots \right\}$

6.2 Improving efficiency

At that step, things are looking bad for $\mathrm{GF}\! \left( 4096 \right)$ , algorithm fails to give any answer in most of the cases ( $2650$ over $4072$ ), and one has to test $436$ useless values before getting the first useful one.

Several sieves are now to be indicated for reducing the set of values to be tested. But, in any case, it should be noticed that the cost of such an efficient exponent is supported once for ever, and is to be compared with the induced time-saving upon future recoveries of Zech's tables.

A first sieve is yields from Fermat's theorem. If $a$ is admissible for a given field $\mathrm{GF}\! \left( q \right)$ , the corresponding $\xi$ is a root of some primitive polynomial of degree $m$ . That polynomial is obviously a divisor of $X^{a}-X-1$ and thus an integer $a$ can not be admissible unless :

An experimental result is that, at least for $p=2$ and $m\leq 13$ , any efficient exponent verifies the stronger criterion :

For composite values of $m$ , especially those divisible by $2$ or $3$ , that result induces a very simple sieve. If $2\, \vert\, m$ , $\mathrm{GF}\! \left( 4 \right)$ is embedded in $\mathrm{GF}\! \left( q \right)$ , thus $X^{2}+X+1$ divides $X^{q-1}-1$ . But proper elements of $\mathrm{GF}\! \left( 4 \right)$ are of order $3$ , therefore $X^{2}+X+1$ divides any $X^{k}-X-1$ where $k=3n+2$ .

Similar considerations can be done when $3\, \vert\, m$ , $4\, \vert\, m$ or $6\, \vert\, m$ . In that cases, the set of values to be tested is reduced by half, as summarized in Table 5.

Table 5: Values that cannot be efficient.

divisibility	values of $k$ to discard
$2\, \vert\, m$	$\left\{ 2\right\} +3\mathbb {Z}$
$3\, \vert\, m$	$\left\{ 3,\, 5\right\} +7\mathbb {Z}$
$4\, \vert\, m$	$\left\{ 2,\, 4,\, 5,\, 8,\, 11,\, 12,\, 14\right\} +15\mathbb {Z}$
$6\, \vert\, m$	$\left\{ 2,\, 3,\, 5,\, 8,\, 10,\, 11,\, 12,\, 14,\, 17,\, 19,\, 20\right\} +21\mathbb {Z}$

6.3 Further values

Table 6: Efficiency of sieves.

m	#adm	#iso	#eff	$\alpha$
8	16	10	8	13
9	48	46	30	11
10	60-2	52	28	57
11	176	176	78	25
12	144-4	92	12	448
13	630	630	126	18
14	756-22	612	42	40
15	1800-x			15
16	2048-x			15981

With these sieves, we get Table 6, where $\char93 adm$ is the number of admissible exponents, given as number of primitive polynomials minus the number of repeated values, $\char93 iso$ is the number of $a$ 's verifying the «criterion of efficiency» (12), $\char93 eff$ is the total number of efficient exponents among them, and $\alpha$ is the smallest efficient exponent for the given $m$ .

6. Efficient exponents

6.1 Random exploration

6.2 Improving efficiency

6.3 Further values