# Fast Algorithms for generalized Discrete Logarithm?

I know the standard algorithms for D-log. Pollard-rho, Baby-step-big-step, Pollig-Hellman, index calculus, etc.

I'm looking for fast algorithms to find a relation for the generalized discrete logarithm:

$$\prod p_i^{a_i} = 1$$

That is, given $$p_i$$, find some non-trivial $$a_i$$ for the above relation.

What are the current best algorithms and runtimes? Any papers or references would be good.

• It is worth mentioning that your equation is closely related to "Discrete Logarithm lattice" of Ducas and Pierrot. You want to construct any lattice point of this lattice. That being said, I believe Ducas + Pierrot's work suggests solving discrete logarithms to do this type of thing (for example, to construct a basis of the lattice).
– Mark
Aug 18 at 1:40

Are you looking for an algorithm that's faster or slower?

For a cyclic group I don't expect this to be faster than standard discrete log.

If you have an algorithm that can solve this generalized discrete log in complexity $$f(n,k)$$ where $$n$$ is the order of the group and $$k$$ is the number of generators you have, you can solve general discrete log in time $$f(n,k)+O(k)$$ by taking a discrete log challenge $$(p,q)$$, generating elements $$p_i=p^{b_i}q^{c_i}$$ by choosing $$b_i,c_i$$ randomly in $$\{0,\dots, n-1\}$$, and passing the $$p_i$$ to the generalized discrete log solver. Given a result $$(a_1,\dots, a_k)$$, you know that if $$q=p^s$$ we have

$$a_1(b_1+sc_1)+\dots + a_k(b_k+sc_k)\equiv 0\mod n$$ and from there it's easy to solve for $$s$$.

Since the best (generic) algorithms we know to solve discrete log have complexity $$\Omega(n^{1/2})$$, then unless $$k\geq n^{1/2}$$, we shouldn't expect a better algorithm for generalized discrete log.

For a non-cyclic group the reduction isn't quite as simple, partly because I'm not sure how the general problem would be defined (should each $$p_i$$ generate a different subgroup? will the solution be unique?). But you might be able to do a reduction as follows: take a discrete log challenge $$(p,q)$$ in a cyclic group $$G$$, and let $$p_i = (p^{b_{i,1}}q^{c_{i,1}},p^{b_{i,2}}q^{c_{i,2}},\dots,p^{b_{i,m}}q^{c_{i,m}})\in G^m$$ for $$i=1$$ to $$k$$, and then pass that to the generalized discrete log solver. A solution will still solve discrete log for you, as well as solve a linear system of the values of $$b_{i,j}$$ and $$c_{i,j}$$. The value of $$m$$ lets you control how many solutions to expect for this generalized DLOG, e.g., if $$m=k$$ and $$n$$ is prime, we expect a unique solution (most of the time).

Overall, I expect this generalized DLOG problem to be harder than standard DLOG.

The reduction doesn't work the other way as far as I can tell, but I think the algorithms should work in mostly the same way. Something like Pollard-Rho will work: find a pseudorandom function $$f$$ from $$G$$ to exponent vectors $$(a_1,\dots, a_k)$$, and iterate the map $$g\mapsto (p_1,\dots, p_k)^{f(g)}$$ (where I mean exponentiate by each element of the vector $$f(g)$$). We can track the total exponent as we iterate, and if we ever find a collision, then we subtract the two cumulative exponent vectors and that solves the problem. Probably this is a non-trivial solution. The birthday paradox tells us that we find a collision in approximately $$O(n^{1/2})$$ iterations.

• My impression is that the reduction is even simpler in the other direction: for all i>1, a standard DLOG solver gives you a relation with a_i=1, a_1≠0 and a_j=0 for j≠1,i, say. (And from that you can recover the entire relation matrix and generate random relations if need be). That's for the cyclic case when p_1 is a generator, say, but the general Abelian case works similarly. Aug 17 at 2:17