# Discrete logarithm problem for multiplicative groups

Hey!

I am trying to find a proper library in order to solve the discrete logarithm problem for multiplicative groups. In fact, I would like to solve it in a group like Z/NZ where N is prime number.

Do you know any library where Index calculus algorithm or Number field sieve is implemented? The functions discrete_log and discrete_log_rho sometimes do not work properly when the prime number is large. (like 100 bits)

For example:

N = 135792089210356248756420345214020892766061623724957744567843809356293439046059 #prime number
factor(N-1) #factor of prime number minus 1
field_N=GF(N,'b')
gen=field_N.multiplicative_generator()
a=gen**44 #212223489
discrete_log(a,gen,n)


When I try to find the exponent 212223489 it tooks much time. In my mind, I was thinking that, due to the factorization of N-1, the discrete logarithm problem will be more easily. I know I am using a "normal" laptop.

Because of this, I was asking about a specific implementation for multiplicative groups.

Thanks!

edit retag close merge delete

It is hard to answer in a specific way in the given generality. When the prime number is large, this is the situation, it is large, and taken large to make it hard to solve the discrete logarithm problem. Implementing a special attack depends a lot on the prime number chosen, and may still fail after a long run. And this is work. Each special case is a special problem. The answer may highly depends on the purpose, than after fixing it on the prime... Please provide code for more, sharing code is sharing effort.

Sort by » oldest newest most voted

The function log of Finite rings calls directly the function znlog of Pari. According to the documentation, znlog uses first the Pohlig-Hellman algorithm, to reduce to groups of prime order. Then it uses a a linear sieve index calculus method. For a faster (and parallel) implementation, you may use CADO-NFS but it will solve the discrete log only in one subgroup each time. So first you have to factorize $p-1$:

sage:  a
3
sage: factor(a.multiplicative_order())
2 * 3 * 73 * 101822137 * 129691841 * 5094796571297629879 * 1536021852403835577250850726481014637179


Then run CADO-NFS on each subgroup:

\$ ./cado-nfs.py -dlp -ell 1536021852403835577250850726481014637179 target=82936225177577666415052331393239668755262693348731690326562114609848154162166 13579208921035624875642034521402089276606162372495774456784380935629343904605

...

Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275...
Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275... passed

...

Info:root: logbase = 7785272685885784582564928906403856210181547208520333383076510590456824439275
Info:root: target = 82936225177577666415052331393239668755262693348731690326562114609848154162166
Info:root: log(target) = 712407062525843960939316924588302612885 mod ell
712407062525843960939316924588302612885


Hopefully in your case is is sufficent to solve in in the largest subgroup since the exponent is small:

sage: ell=1536021852403835577250850726481014637179
sage: inverse_mod(1404106513053697738808612862784757866144,ell)*712407062525843960939316924588302612885 % ell
212223489


You would have finished the Pohlig-Hellman algorithm for larger exponent values.

more