mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2013-07-12, 01:36   #1
Lakshmi
 
Lakshmi's Avatar
 
Jul 2013

1 Posts
Default Software for discrete logarithms

I am not sure where this message goes.

I am thinking of implementing a software for performing discrete logarithms over large prime fields, by some advanced algorithms like Index Calculus, Function Field Sieve.

I would like to seek an advice if it will be useful to everyone, and if there is a need for such a software when compared to currently existing ones that can handle this problem over large prime field faster.

I have used Discrete Logarithm software from http://www.alpertron.com.ar/DILOG.html, which performs Pohlig-Hellman algorithm capable of handling problem if the modulus is composite, composed of small prime factors, say < 1015, but is incapable of handling large prime modulus fields.

Lakshmi
Lakshmi is offline   Reply With Quote
Old 2013-07-12, 11:22   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

There is very little available software that can solve this problem. The only public package I know about is GDLOG. Also, the CADO-NFS project is building a function-field sieve capability on top of their number field sieve code, and the developers are very responsive if you post to the cado-nfs-discuss mailing list.

People here actually are basically not interested at all in solving general discrete logarithm problems. That's actually a bit surprising given how much interest this forum has in integer factorization.
jasonp is offline   Reply With Quote
Old 2013-10-07, 01:24   #3
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

See also http://www.cs.toronto.edu/~cvs/dlog/
maxal is offline   Reply With Quote
Old 2013-10-07, 12:15   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by jasonp View Post
People here actually are basically not interested at all in solving general discrete logarithm problems. That's actually a bit surprising given how much interest this forum has in integer factorization.
Why do you find it surprising? There are many theorems that involve
factorization. There are applications for factoring. There are sets
of numbers whose factorization is "interesting" and/or useful.

What similar things are there for DL?

There are ECDL challenge problems, but NFS is not applicable.
R.D. Silverman is offline   Reply With Quote
Old 2013-10-07, 12:17   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Why do you find it surprising? There are many theorems that involve
factorization. There are applications for factoring. There are sets
of numbers whose factorization is "interesting" and/or useful.

What similar things are there for DL?

There are ECDL challenge problems, but NFS is not applicable.
Allow me to add:

While Dl over finite fields is used for breaking DH, DSA, and El-Gamal,
these crypto primitives are not used to nearly the same extent as RSA.
R.D. Silverman is offline   Reply With Quote
Old 2013-12-09, 15:53   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110000010102 Posts
Default



We are trying to solve k for \alpha^k=\beta \pmod{p}, p prime < 2^64, to be used in a sieve. Currently, we are using Pollard's Rho, where \alpha has to be a generator of Z_p^*. Is there a fast algorithm for a non-generator we can use, faster than brute force multiplication and multiplicative order calculation?

Last fiddled with by paulunderwood on 2013-12-09 at 15:54
paulunderwood is offline   Reply With Quote
Old 2013-12-09, 16:13   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by paulunderwood View Post


We are trying to solve k for \alpha^k=\beta \pmod{p}, p prime < 2^64, to be used in a sieve. Currently, we are using Pollard's Rho, where \alpha has to be a generator of Z_p^*. Is there a fast algorithm for a non-generator we can use, faster than brute force multiplication and multiplicative order calculation?
I'm not sure I understand something. First you state that alpha is a
generator, then you ask about a fast method for a non-generator.
Please clarify. If alpha is not a primitive root, then Beta might not
be in its orbit. (i.e. no solution)

Pohlig-Hellman should probably work, depending on the factorization of
p-1.

If not, then the choices are: an O(sqrt(p)) method
such as Pollard Rho [or Pollard Kangaroo if you run in parallel], or
Baby Step/Giant Step

OR:

While I have never used NFS on a field this small, it may not be too bad.
Of course, implementing NFS yields a thundering amount of code.

If anyone else has better suggestions I would love to hear about them.
R.D. Silverman is offline   Reply With Quote
Old 2013-12-09, 16:26   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

E0A16 Posts
Default

We have the cases where \alpha is a generator for some prime pi covered by Pollard Rho. However, for some prime pj, \alpha is not a generator. (In our sieve, \alpha is a fixed base.)

Thanks for you pointers, RDS. Will Pohlig-Hellman work for a non-generator \alpha -- i.e. solve k if \beta is in \alpha's orbit or say "nay" if not?

Last fiddled with by paulunderwood on 2013-12-09 at 16:40
paulunderwood is offline   Reply With Quote
Old 2013-12-09, 16:43   #9
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

To eliminate obvious cases with no solutions, I suggest first to compute the multiplicative order $q$ (by factoring p-1 and eliminating its prime divisors as needed) of \alpha and test whether $\beta^q \equiv 1\pmod{p}$. If this congruence does not hold, there are no solutions.
maxal is offline   Reply With Quote
Old 2013-12-10, 01:52   #10
Citrix
 
Citrix's Avatar
 
Jun 2003

1,579 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Will Pohlig-Hellman work for a non-generator \alpha -- i.e. solve k if \beta is in \alpha's orbit or say "nay" if not?
Yes this should work, as maxal suggested. The fastest method would be combining pollard rho with Pohlig-Hellman (based on factorization of p-1).

Even for cases where there is a solution (beta is in alphas orbit) Pohlig-Hellman with Pollard rho will be faster (depending on p-1 factorization) than Pollard rho by itself.


Baby step-Giant step is better than Pollard rho as it is definitive (gives you a yes or no answer) over a range of n but requires significantly more memory. Baby step-Giant step can also be combined with Pohlig-Hellman.
Citrix is offline   Reply With Quote
Old 2013-12-16, 20:27   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

E0A16 Posts
Default

Quote:
Originally Posted by maxal View Post
To eliminate obvious cases with no solutions, I suggest first to compute the multiplicative order $q$ (by factoring p-1 and eliminating its prime divisors as needed) of \alpha and test whether $\beta^q \equiv 1\pmod{p}$. If this congruence does not hold, there are no solutions.
Thanks. This is very useful. I can give a tighter condition: $\beta^{\frac{q}{g}} \equiv 1\pmod{p}$ where g is the g.c.d. of q and k. Did you mean this?

Last fiddled with by paulunderwood on 2013-12-16 at 20:27
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help with discrete logarithm pinnn Information & Answers 32 2017-11-08 00:08
Can discrete logarithms / factoring be done in P (i.e., deterministic polynomial time)? Raman Factoring 1 2016-05-23 13:44
Pollard Rho Discrete Log rogue Math 6 2012-09-26 11:20
Discrete logarithm software Unregistered Information & Answers 39 2012-04-27 20:08
On discrete logs kpatsak Math 1 2008-02-19 04:44

All times are UTC. The time now is 14:19.

Fri Mar 5 14:19:46 UTC 2021 up 92 days, 10:31, 1 user, load averages: 2.70, 2.62, 2.66

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.