Finite Fields and Zech's Logarithms

P-L. Douillet

IBP-Masi 1994/14: Rapport de Recherche Masi / Masi research reports
19 pages - Avril/April 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Finite Fields and Zech's Logarithms

Résumé : 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 GF(q). Cet algorithme, ne mettant en oeuvre que des opérations élémentaires sur les entiers, a 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 Claus Huber qui réduit (grosso modo) l'espace disque requis de q à 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 : il est donc raisonnable d'en entreprendre une recherche systématique. 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<= 13.

Abstract : It is shown how a single integer, "efficient exponent" for a given finite field, can be taken as the starting point of a probabilistic algorithm that rebuilds the Zech table of GF(q) with only simple arithmetic on integers, i.e. in a time comparable with loading from a tape or a disk.
That algorithm completes the Claus Huber's method of storage, wich roughly reduces the storage burden from q to q/6m when the Zech table is in use. Now, tables corresponding to fields not actually under study can be quite completely removed.
It is shown that these "efficients 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.

Publications internes Masi 1994 / Masi research reports 1994