Watson Ladd on Tue, 10 Jun 2025 18:43:22 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Reimplementing the cubic sieve faster



On Tue, Jun 10, 2025, 9:33 AM Laël Cellier <lael.cellier@laposte.net> wrote:
As as supplemental question, is it possible to shrink the factor base if
we know the discrete logarithm is below a specific bound ?

No. But two grumpy giants and baby can be of use here if the bound is small.

Or more generally, to speed up the algorithm beside in the end solving
the linear system modulo ((P−1)÷suborder) ?

Le 03/06/2025 à 00:20, Bill Allombert a écrit :
> 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.