Discrete logarithm computations over finite fields using Reed-Solomon codes
Résumé
Cheng and Wan have related the decoding of Reed-Solomon codes to the computation of discrete logarithms over finite fields, with the aim of proving the hardness of their decoding. In this work, we experiment with solving the discrete logarithm over GF(q^h) using Reed-Solomon decoding. For fixed h and q going to infinity, we introduce an algorithm (RSDL) needing O~(h! q^2) operations over GF(q), operating on a q x q matrix with (h+2) q non-zero coefficients. We give faster variants including an incremental version and another one that uses auxiliary finite fields that need not be subfields of GF(q^h); this variant is very practical for moderate values of q and h. We include some numerical results of our first implementations.
Cheng et Wan ont relié le décodage des codes de Reed-Solomon au calcul de logarithmes discrets dans les corps finis, dans le but de prouver la difficulté de leur décodage. Dans cet article, nous expérimentons le calcul de logarithmes discrets sur GF(q^h) en utilisant des codes de Reed-Solomon. Pour h fixé et q tendant vers l'infini, nous présentons un algorithme, appelé RSDL, qui requiert O~(h! q^2) opérations su GF(q), opérant sur une matrice qxq avec (h+2)q coefficients non-nuls. Nous donnons des variantes plus rapides, parmi lesquelles une version incrémentale et une autre utilisant des corps finis auxiliaires qui ne sont pas nécessairement des sous-corps du corps GF(q^h); cette variante est très pratique pour des valeurs modérées de q et h. Nous incluons également quelques résultats numériques obtenus avec notre première implantation.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...