Ask Your Question
1

Discrete logarithm problem for multiplicative groups

asked 2022-05-17 14:49:36 +0100

alberto26 gravatar image

updated 2022-05-20 15:30:26 +0100

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 flag offensive close merge delete

Comments

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.

dan_fulea gravatar imagedan_fulea ( 2022-05-17 21:46:31 +0100 )edit

I edited the question! Thanks!

alberto26 gravatar imagealberto26 ( 2022-05-19 17:01:30 +0100 )edit

You may like to try gp.znlog.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-05-20 15:58:38 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
0

answered 2022-07-30 10:31:53 +0100

Sylvain gravatar image

updated 2022-07-30 11:05:43 +0100

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

2 followers

Stats

Asked: 2022-05-17 14:49:36 +0100

Seen: 1,712 times

Last updated: Jul 30 '22