Discussion related to cado-nfs

[Laël Cellier <lael.cellier@grenoble-inp.org>]

Hemm noo…

ECM is not beating NFS for these parameters; you need an expected ~40000 runs with B1=110000000  to find a 191-bit factor, where each run takes ~1 minute at ~4 GHz, which is only faster if you have an incredibly high amount of parallelism.

And then it wouldn’t happen for less than 100€…

Unless you heard about modern fpga implementations.

Sincerely,

Le 11/03/2024 à 7:53 AM, Pierrick Gaudry a écrit :

> Hi,
>
> ECM is an almost perfectly parallelizable factoring algorithm.
> Its complexity is in L(1/2) instead of L(1/3) for GNFS, and in practice
> it can extract prime factors of only a few dozen of digits. For 115 digits
> RSA numbers, it is certainly not the fastest method.
>
> You can have a look at GMP-ECM. Give it a try with appropriate parameters
> (see https://members.loria.fr/PZimmermann/records/ecm/params.html), and
> you will get an estimate of the cost.
>
> Note the total time of ECM before finding a factor is very probabilistic.
>
> Regards,
> Pierrick
>
>
> On Mon, Mar 11, 2024 at 12:34:29AM +0100, Laël Cellier wrote:
> > As everybody here knows, the ɢɴꜰꜱ is the most efficient algorithm for
> > factoring numbers formed of roughly equal in length composites.
> >
> > But it’s linear Algebra/sequential parts means (If I’m not wrong), that it
> > requires at least 9 minutes on current hardware to factor semi‑primes formed
> > of composites of roughly equal length (in the case of 382 bits semi‑primes
> > the Linear part takes 6 to 10 minutes).
> >
> > Are there less efficient algorithms but by being more parallelizable, that
> > would allow to solve batch of such semi‑primes faster using more resources ?
> > (though not prohibitively costly). If yes, it would be good for ᴄᴀᴅᴏ to
> > support them…
> >
> > The aim is part of a small competition where the reward goes to the first
> > who answers. The fact the record is still 9 minutes for 382 bits semi‑prime
> > seems to tell there’s no solution : but there’s currently only 3
> > participants in the race.
> >
> > Sincerely,
> >       
>