Finite Fields and Zech's Logarithms

It is shown how a single integer "efficient exponent" for a given finite field, can be taken as the starting point or a probabilistic algorithm that rebuilds the Zech table or $\mathrm{GF}\! \left( q \right)$ with only simple arithmetic on integers, i.e. in a time comparable with loading from a tape or a disk.

That algorithm completes the Klaus Huber's method of storage [6, 5] which reduces the storage burden from $q=p^{m}$ to (roughly) $q/6m$ when the Zech table is in use. Now, tables corresponding to fields not being actually under study can be quite completely removed.

It is shown that these "efficient exponents" are not too rare, enabling a systematic search, and several sieves are given to speed up that search. Values are given for small fields.

Nous montrons comment un entier naturel, "exposant efficace" pour un corps fini donné, peut être pris comme point de départ d'un algorithme probabiliste permettant de reconstruire une table de Zech du corps $\mathrm{GF}\! \left( q \right)$ . Cet algorithme, ne mettant en oeuvre que des opérations élémentaires sur les entiers, possède une vitesse d'exécution comparable avec un chargement depuis un disque.

Cet algorithme complète la méthode de stockage développée par Klaus Huber [6, 5] qui réduit (grosso modo) l'espace disque requis de $q=p^{m}$ à $q/6m$ quand la table est en cours d'utilisation. Avec notre algorithme, les tables qui ne sont pas en cours d'utilisation peuvent être purement et simplement effacées.

Nous montrons que ces "exposants efficaces" ne sont pas trop rares : une recherche systématique peut donc être entreprise. De plus, nous donnons des cribles permettant d'accélérer cette recherche.

Des résultats numériques sont donnés pour les corps $2^{m}$ avec $m<11$ .

Finite Fields and Zech's Logarithms

Résumé:

Résumé: