Re: Reimplementing the cubic sieve faster

The problem in my use case is the prime field is 500 bits large while 
the suborder is around 160Bits large : so it’s a bit too large for 
pollard rho and ʙʙɢꜱ

Le 10/06/2025 à 18:43, Watson Ladd a écrit :
>
>
> On Tue, Jun 10, 2025, 9:33 AM Laël Cellier <[email protected]> 
> 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.
>