Re: Reimplementing the cubic sieve faster

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Mon, Jun 02, 2025 at 11:58:31PM +0200, Laël Cellier wrote:
> Problem, is in my case it doesnt integrate with Pari-ɢᴘ.

You can always use extern(), thats does not seem to be a practical problem.

> How do I solve the linear system ?

This is the hard part.
cado-nfs sparse linear algebra is much faster than PARI.
In fact PARI quadratic sieve would probably be fast enough
if cado-nfs sparse linear algebra was used.

> Stupid question, but when you write about picking a triplet such a+b+c=0, do
> you mean picking them mod p ?

No, a,b,c are much smaller than p, so |a+b+c| < p.

Cheers,
Bill.