Discussion related to cado-nfs

[Pierrick Gaudry <pierrick.gaudry@loria.fr>]

As you say, the techniques used in the family of algorithms with
quasipolynomial compexity are dedicated to small characteristics.  They
have a O(p), at the very least, in their complexity, which makes them
completely useless in what we call medium characteristic. And this is not
a matter of having no access to the implementation: it's really about the
algorithm not working efficiently in that case.

As for using elliptic curves in this context, actually the idea was first
considered a long time ago, precisely in the medium characteristic case, by
Couveignes and Lercier:
  https://arxiv.org/abs/0802.0282

Unfortunately, no practical speed-up is to be expected. And again, this
is not a matter of "there is no free implementation available", but more
a lack of algorithm.

In summary, we have already explored what we suggest, and we have
absolutely no hope to make it work in the medium characteristic case.
New ideas are needed.

But, as usual, feel free to investigate more. 

Pierrick

On Sat, Nov 30, 2024 at 10:19:22AM +0100, Laël Cellier wrote:
> Hi,
> 
> In the recent years, several algorithms were proposed to leverage elliptic
> curves for lowering the degree of a finite field and thus allow to solve
> discrete logairthm modulo their largest suborder/subgroup instead of the
> original far larger finite field. https://arxiv.org/pdf/2206.10327
> <https://arxiv.org/pdf/2206.10327> in part conduct a survey about those
> methods. Espescially since I don’t see why medium chararcteristics would be
> prone to fall in the trap being listed by the paper.
> 
> I do get the whole /small characteristics/ alogrithms complexity makes those
> papers unsuitable for computing discrete logarithms in finite fields of
> large charateristics, but what does prevent applying the /descent/even
> degree shrinking part/ to medium characteristics ?
> 
> Of course, a key problem is no implementation for solving discrete
> logarithms in finite fields of small characteristics in near polynomial time
> is public (feel free to correct me) and it would take an amount of effort to
> bring this to ᴄᴀᴅᴏ‑ɴꜰꜱ that I can’t provide due to lack of knowlwedge.
> 
> Sincerely,