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!
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.
I edited the question! Thanks!
You may like to try
gp.znlog
.