Discussion related to cado-nfs

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

Hi Laël,

I didn't know this paper. I had a quick look. Here are my thoughts:

- this is an L(1/2) algorithm, while NFS is an L(1/3) algorithm.
  Asymptotically, this can not win against NFS. The crossover depends on
  implementations, but usually it is around 100 digits inputs.
- the improve the individual logarithm step, which is the less costly
  among all the steps.
- actually, I am not sure this is a real improvement compared to the
  naive approach.
- the individual logarithm step is different in NFS, so that the
  technique can not be transposed to this algorithm.

To conclude: I might be wrong (of course), but I don't think this has any
chance to be interesting for large scale computations.

Regards,
Pierrick

On Sun, Nov 24, 2024 at 04:59:32PM +0100, Laël Cellier wrote:
> Bonjour,
> 
> I was reading this paper : https://arxiv.org/pdf/2409.08784. Although it
> contains rants and the timings are questionable unless they only have their
> phones, the underying idea is to pick up several factor bases instead of 1
> in order to shrink the number of individual discrete logarithms for a given
> target.
> 
> Now, I’m only a beginner, but is this an idea that can be useful for more
> advanced algorithms ? They give full step by step of their textbook
> algorithm.
> 
> Cordialement,
> 
>