Software for discrete logarithms

Lakshmi · 2013-07-12, 01:36

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 < 10¹⁵, but is incapable of handling large prime modulus fields.

Lakshmi

jasonp · 2013-07-12, 11:22

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.

maxal · 2013-10-07, 01:24

See also http://www.cs.toronto.edu/~cvs/dlog/

R.D. Silverman · 2013-10-07, 12:15

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.

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

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.

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.

paulunderwood · 2013-12-09, 15:53

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?

R.D. Silverman · 2013-12-09, 16:13

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
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.

paulunderwood · 2013-12-09, 16:26

We have the cases where $\alpha$ is a generator for some prime p_i covered by Pollard Rho. However, for some prime p_j, $\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?

maxal · 2013-12-09, 16:43

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.

Citrix · 2013-12-10, 01:52

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.

paulunderwood · 2013-12-16, 20:27

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?

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 < 10¹⁵, but is incapable of handling large prime modulus fields. Lakshmi

2013-12-09, 15:53	#6
paulunderwood Sep 2002 Database er0rr 7012₈ 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:26	#8
paulunderwood Sep 2002 Database er0rr 111000001010₂ Posts	We have the cases where $\alpha$ is a generator for some prime p_i covered by Pollard Rho. However, for some prime p_j, $\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

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

2013-07-12, 11:22	#2
jasonp Tribal Bullet Oct 2004 6716₈ 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 2²·3²·7 Posts	See also http://www.cs.toronto.edu/~cvs/dlog/

2013-12-09, 16:43	#9
maxal Feb 2005 2²·3²·7 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.