Re: Reimplementing the cubic sieve faster

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

On Mon, Jun 02, 2025 at 04:47:53PM +0200, Laël Cellier wrote:
> 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.

Well you can just use cado-nfs instead, it can do discrete logarithms too,
and is faster than the cubic sieve.

> Also in the formulas you gave, what’s the factor base ?

All the prime numbers less than B for some B

> What do
> you mean about finding non trivial factorisation since it’s about computing
> a discrete logarithm ? 

if you can write

(x+a*y)*(x+b*y)*(x+c*y) = p1*p2*...*pj
then
log(x+a*y)+log(x+b*y)+log(x+c*y) = log(p1)+log(p2)+..+log(pj)

so you have found a relation between the discrete logarithms.
Once you have enough relation you can solve the linear system.

> Is finding relations about computing many value of
> x+y*a ? How to select the values of a ? 

Take all the |a| < C  with C ~ 2*B^(1/3).

Cheers,
Bill