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$
  • $\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$ – Don Fanucci Jan 15 '18 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 Jan 15 '18 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$ – Don Fanucci Jan 15 '18 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 Jan 15 '18 at 17:34
  • $\begingroup$ Now I understand. Is there something I can do to solve this? @fgrieu $\endgroup$ – Don Fanucci Jan 15 '18 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.