Discussion related to cado-nfs

[Paul Leyland <paul.leyland@gmail.com>]

See also the discussion at 
https://mersenneforum.org/showthread.php?t=29410 for further information 
about the background for this request and suggestions as to how it may 
be addressed.


Paul

On 11/03/2024 06:53, Pierrick Gaudry wrote:
> 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,