A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913702230360064 |
|---|---|
| author | Lido, Guido |
| author_facet | Lido, Guido |
| contents | We describe a provably quasi-polynomial algorithm to compute discrete logarithms in the multiplicative groups of finite fields of small characteristic, that is finite fields whose characteristic is logarithmic in the order. We partially follow the heuristically quasi-polynomial algorithm presented by Barbulescu, Gaudry, Joux and Thome'. The main difference is to use a presentation of the finite field based on elliptic curves: the abundance of elliptic curves ensures the existence of such a presentation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_10327 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic Lido, Guido Number Theory 11T71, 94A60, 11G25 We describe a provably quasi-polynomial algorithm to compute discrete logarithms in the multiplicative groups of finite fields of small characteristic, that is finite fields whose characteristic is logarithmic in the order. We partially follow the heuristically quasi-polynomial algorithm presented by Barbulescu, Gaudry, Joux and Thome'. The main difference is to use a presentation of the finite field based on elliptic curves: the abundance of elliptic curves ensures the existence of such a presentation. |
| title | A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic |
| topic | Number Theory 11T71, 94A60, 11G25 |
| url | https://arxiv.org/abs/2206.10327 |