Re: Reimplementing the cubic sieve faster

Problem, is in my case it doesnt integrate with Pari-ɢᴘ.

How do I solve the linear system ?

Stupid question, but when you write about picking a triplet such 
a+b+c=0, do you mean picking them mod p ?

Le 02/06/2025 à 22:07, Bill Allombert a écrit :
> 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