Re: Reimplementing the cubic sieve faster

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

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.