A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic

Abstract : In this paper, we describe a new algorithm for discrete logarithms in small characteristic. This algorithm is based on index calculus and includes two new contributions. The first is a new method for generating multiplicative relations among elements of a small smoothness basis. The second is a new descent strategy that allows us to express the logarithm of an arbitrary finite field element in terms of the logarithm of elements from the smoothness basis. For a small characteristic finite field of size Q = pn, this algorithm achieves heuristic complexity LQ(1/4 + o(1)). For technical reasons, unless is already a composite with factors of the right size, this is done by embedding double-struck FQ in a small extension with double-struck FQe with e ≤ 2⌈logpn⌉. © 2014 Springer-Verlag.
Document type :
Conference papers
Complete list of metadatas

https://hal.uvsq.fr/hal-02177225
Contributor : Équipe Hal Uvsq <>
Submitted on : Monday, July 8, 2019 - 5:12:33 PM
Last modification on : Tuesday, July 9, 2019 - 1:27:43 AM

Links full text

Identifiers

Collections

Citation

A. Joux. A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic. 20th International Conference on Selected Areas in Cryptography, SAC 2013, Aug 2013, Burnaby, BC, Colombia. pp.355-379, ⟨10.1007/978-3-662-43414-7_18⟩. ⟨hal-02177225⟩

Share

Metrics

Record views

35