Re: Reimplementing the cubic sieve faster

Cado-nfs should be eating the prime field for breakfast at that size



On Tue, Jun 10, 2025, 9:47 AM Laël Cellier <[email protected]> wrote:

> 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.
>>
>>