-1
$\begingroup$

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<P-1 \in \mathbb{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$

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$ $\endgroup$
    – J. Doe
    Commented May 6, 2019 at 16:51
  • 1
    $\begingroup$ 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) $\endgroup$
    – poncho
    Commented May 6, 2019 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.