کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8895606 | 1630350 | 2018 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Factor base discrete logarithms in Kummer extensions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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 Fq2(qâ1)=Fq2[x]/(xqâ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 OË(q1+θ) (or algebraic complexity OË(qθ)) to compute discrete logarithms of all the elements in the factor base {x+α|αâFq2}, where θ<2.38 is the matrix multiplication exponent over rings. Given additional time OË(q4), we can compute discrete logarithms of at least Ω(q3) 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 log2â¡(q2(qâ1))â¤5134, and provide theoretical supporting evidences.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Finite Fields and Their Applications - Volume 53, September 2018, Pages 205-225
Journal: Finite Fields and Their Applications - Volume 53, September 2018, Pages 205-225
نویسندگان
Dianyan Xiao, Jincheng Zhuang, Qi Cheng,