Paper 2015/859

Factor Base Discrete Logarithms in Kummer Extensions

Dianyan Xiao, Jincheng Zhuang, and Qi Cheng

Abstract

The discrete logarithm over finite fields of small characteristic can be solved much more efficiently than previously thought. This algorithmic breakthrough is based on pinpointing relations among the factor base discrete logarithms. In this paper, we concentrate on the Kummer extension $ \F_{q^{2(q-1)}}=\F_{q^2}[x]/(x^{q-1}-A). $ It has been suggested that in this case, a small number of degenerate relations (from the Borel subgroup) are enough to solve the factor base discrete logarithms. We disprove the conjecture, and design a new heuristic algorithm with an improved bit complexity $ \tilde{O}(q^{1+ \theta} ) $ (or algebraic complexity $\tilde{O}(q^{\theta} )$) to compute discrete logarithms of all the elements in the factor base $\{ x+\alpha | \alpha \in \F_{q^2} \} $, where $ \theta<2.38 $ is the matrix multiplication exponent over rings. Given additional time $ \tilde{O} (q^4), $ we can compute discrete logarithms of at least $ \Omega(q^3) $ many monic irreducible quadratic polynomials. We reduce the correctness of the algorithm to a conjecture concerning the determinant of a simple $ (q+1)$-dimensional lattice, rather than to elusive smoothness assumptions. We verify the conjecture numerically for all prime powers $ q $ such that $ \log_2(q^{2(q-1)}) \leq 5134 $, and provide theoretical supporting evidences.

Note: 19 pages, writing revised, appendix modified

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Discrete logarithmsFinite fieldsKummer extensionCharacter Sum
Contact author(s)
zhuangjincheng @ iie ac cn
History
2017-02-27: revised
2015-09-06: received
See all versions
Short URL
https://ia.cr/2015/859
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/859,
      author = {Dianyan Xiao and Jincheng Zhuang and Qi Cheng},
      title = {Factor Base Discrete Logarithms in Kummer Extensions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/859},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/859}},
      url = {https://eprint.iacr.org/2015/859}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.