Re: Reimplementing the cubic sieve faster

[Laël Cellier <lael.cellier@laposte.net>]

In my case, p is 255bits large safe prime and I need to solve multiple 
discrete logarithm with such kind of p hence why 
https://www.sciencedirect.com/science/article/pii/S0747717113001703 
would be relevant. Also in the formulas you gave, what’s the factor 
base ? What do you mean about finding non trivial factorisation since 
it’s about computing a discrete logarithm ? Is finding relations about 
computing many value of x+y*a ? How to select the values of a ? should 
it be purely done purely randomly based on size ?

When picking a triplet such a+b+c=0, do you mean picking mod p ?

Sorry for having problems to understand how cubic sieve works…

Le 02/06/2025 à 14:56, Bill Allombert a écrit :
> On Mon, Jun 02, 2025 at 11:44:12AM +0200, Laël Cellier wrote:
> > Bonjour,
> >
> > as you know, the cubic sieve already exist in Pari‑ɢᴘ, but as far I
> > understand, it lacks the improvement of
> > https://www.sciencedirect.com/science/article/pii/S0747717113001703 for
> > computing the initial cubic sieve congruence far more faster.
> The cubic sieve is implemented in PARI for F_p^n for small p and not for
> F_p for large p. In PARI case, there is no need to search for initial cubic
> sieve congruence.
>
> > A part of the
> > problem, is I fail to understand how to implement the main algorithm in any
> > language (which of course include pari/ɢᴘ).
> >
> > Would it be possible to get help for understanding how exactly to perform
> > the sieving and relation collection steps ? My use case would be on prime
> > fields…
> Start with  x^3 = y^2*z  mod p with x,y and z of size (p^(1/3))
>
> Add to you factor basis all the elements (x+y*a) for all very small 'a'.
>
> Now pick a triplet (a,b,c) such that a+b+c=0. It follows
>
> (x+a*y)*(x+b*y)*(x+c*y) = x^3   + (a*b+a*c+a*c)*y^2*x + a*b*c*y^3
> (x+a*y)*(x+b*y)*(x+c*y) = y^2*z + (a*b+a*c+a*c)*y^2*x + a*b*c*y^3 mod p
>                          = y^2*(z+ (a*b+a*c+a*c)*x + a*b*c*y) mod p
>
> Thus we get a non-trivial factorization of (x+a*y)*(x+b*y)*(x+c*y) over the factor basis
> as soon as we find a factorization of z+(a*b+a*c+a*c)*x+a*b*c*y over the factor basis.
>
> Since a,b,c are very small and x,y,z are of size p^(1/3)
> z+(a*b+a*c+a*c)*x+a*b*c*y is of size p^(1/3)
>
> The point is that a number of size p^(1/3) is much more likely to be smooth
> than a number of size p^(1/2) as used by the quadratic sieve.
>
> Cheers,
> Bill.