Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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.
