mersenneforum.org Software for discrete logarithms
 Register FAQ Search Today's Posts Mark Forums Read

 2013-07-12, 01:36 #1 Lakshmi     Jul 2013 1 Posts 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
 2013-07-12, 11:22 #2 jasonp Tribal Bullet     Oct 2004 67168 Posts 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.
 2013-10-07, 01:24 #3 maxal     Feb 2005 FC16 Posts
2013-10-07, 12:15   #4
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by jasonp 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.

2013-10-07, 12:17   #5
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by R.D. Silverman 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.

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.

 2013-12-09, 15:53 #6 paulunderwood     Sep 2002 Database er0rr 37×97 Posts 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
2013-12-09, 16:13   #7
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by paulunderwood 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
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.

 2013-12-09, 16:26 #8 paulunderwood     Sep 2002 Database er0rr 1110000001012 Posts 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
 2013-12-09, 16:43 #9 maxal     Feb 2005 FC16 Posts 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.
2013-12-10, 01:52   #10
Citrix

Jun 2003

1,579 Posts

Quote:
 Originally Posted by paulunderwood 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.

2013-12-16, 20:27   #11
paulunderwood

Sep 2002
Database er0rr

37×97 Posts

Quote:
 Originally Posted by maxal 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

 Similar Threads Thread Thread Starter Forum Replies Last Post pinnn Information & Answers 32 2017-11-08 00:08 Raman Factoring 1 2016-05-23 13:44 rogue Math 6 2012-09-26 11:20 Unregistered Information & Answers 39 2012-04-27 20:08 kpatsak Math 1 2008-02-19 04:44

All times are UTC. The time now is 11:29.

Thu Feb 25 11:29:33 UTC 2021 up 84 days, 7:40, 0 users, load averages: 1.91, 1.65, 1.48