Re: Reimplementing the cubic sieve faster
Laël Cellier <[email protected]>
| Newsgroups | gmane.comp.mathematics.pari.user |
|---|---|
| Message-ID | <[email protected]> |
And if there’s many more numbers ? Turns out then that solving on the first 160 bits in subexponential time is prefered… Also what does it means to have a number below a factor base with finite fields having several elements ? Le 10/06/2025 à 19:21, Watson Ladd a écrit : > 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. >>