Laël Cellier on Mon, 02 Jun 2025 23:58:43 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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