Discussion related to cado-nfs

[Laël Cellier <lael.cellier@laposte.net>]

Bonjour,

yes, but my idea was never to use it for the small characteristics index 
calculus methods, so nevertheless I want details about how the Elliptic 
curve part simplification complexity… I’m only a student, so there’s lot 
of things I don’t understand,

Cordialement,

Le 01/12/2024 à 15:18, Pierrick Gaudry a écrit :
> 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,