# Is there a fast way to solve $k = n \cdot g^a \mod P$? (get $a$ for unknown $n$)

Would a factor besides the normal discrete logarithm problem increase or decrease the solving time?

$$k = n \cdot g^a \mod P$$

with given $$k,g,P$$ and the knowledge $$P= 2 \cdot N \cdot f+1$$, while $$f$$ can be a product out of other primes. The factor $$n. The generator $$g$$ can generate a group with max size of $$N$$.
How can we solve this?

Harder than solving the normal: $$k' = h^a \mod Q$$, with h prime rooot of $$Q$$?

edit: forgot to mention at least two equations need to be solved with same $$n$$
$$k' = n \cdot g^b \mod P$$
or one without
$$k' = k \cdot g^c \mod P$$

$$k = n \cdot g^a \mod P$$

How can we solve this?

It is trivial to find $$(n, a)$$ pairs that satisfy this relation; select an arbitrary $$a$$ and compute $$n = k g^{-a} \bmod P$$; that's a solution.

Now, that'll give you $$ord(g)$$ distinct solutions; if you have a specific solution in mind, you have no way to telling which one it is. However, depending on how the solution is used, it might not matter...

• Thanks for response, always forgetting your can just apply simple transformation at mod functions. I think in use case it does matter. There a 2nd equation is given with $k'=n \cdot g^b \mod P$. So $a,b$ with same $n$ need to be found or $k'=k \cdot g^c$ – J. Doe May 6 '19 at 16:51
• If you extend the question to "solve a solution $a, b, n$ to the simultaneous equations $k = n \cdot g^a \bmod P$, $k' = n \cdot g^b \bmod P$", then there are still multiple solutions; however finding one solution is now equivalent to the DLog problem (equivalent in the sense that an oracle to solve one problem allows you to solve the other) – poncho May 6 '19 at 18:39