1
$\begingroup$

This question is not directly about cryptography, but I feel that it is most suitable for this site.

DLOG problem: Given a prime $p$, $g$ a multiplicative generator of $\mathbb{Z}_p^\star$ and an element $y\in\mathbb{Z}_p^\star$ find $0\leq x< p-1$ such that $g^x=y$.

Suppose we know that $p$ is a prime of the form $10^n+1$.

Give an efficient algorithm for solving the DLOG problem in this scenario.

I observed that we can find using brute force the order of the element $y$ in time $O(n^2)$ which is poly-log in $p$. I don’t know how to proceed.

$\endgroup$
6
  • $\begingroup$ @fgrieu the order of $g$ is $p-1$ so I claim that $x\cdot o(g^x)=p-1\ =0\ (\text{mod}\ p-1)$? or just extracting $x=(p-1)/o(g^x)$? $\endgroup$ Commented Jan 15, 2018 at 16:12
  • $\begingroup$ Remark: We know only $n=1$ and $n=2$ such that $p=10^n+1$ is prime, it must be of the form $n=2^k$, and there's wide consensus $2\le k\le24$ won't do. We can still reason on what if we knew another such $n$, small enough that computations modulo $p$ are feasible. I had missed "$g$ a multiplicative generator.." sorry about that. Still, we know that the order of $g$ is a power of 10. $\endgroup$
    – fgrieu
    Commented Jan 15, 2018 at 16:41
  • $\begingroup$ @fgrieu I understand that such primes that are small are rare. But is it true that $x=(p−1)/o(g^x)$? $\endgroup$ Commented Jan 15, 2018 at 16:45
  • $\begingroup$ No. Counterexample: $p=11$, $g=2$, $o(g)=o(2)=10=p-1$, $x=3$, $g^x=8$, $o(8)=10$, $(p-1)/o(g^x)=10/10=1\ne 3=x$. $\endgroup$
    – fgrieu
    Commented Jan 15, 2018 at 17:34
  • $\begingroup$ Now I understand. Is there something I can do to solve this? @fgrieu $\endgroup$ Commented Jan 15, 2018 at 17:42

0

Your Answer

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

Browse other questions tagged or ask your own question.