Let $p = kq + 1$ and $q$ be primes such that $log$ $q = n$, $log$ $k = n$ and such that the bit size of every prime factor of $k$ is bounded by $log$ $n$. Let $g$ be a generator of the unique subgroup of $Z^*_p$ of order $q$.

$x \in$ $Z_q$ is picked randomly and you get $y = g^x$.

You may ask any number of questions of the form $u \in Z^*_p$, which will be answered by $u^x$ $mod$ $p$.

How would you go ahead to compute $x$ efficiently?

Solving the discrete logarithm problem would be nice, but I guess that's out of the question.. :)

I don't get which properties that's given to use, (probably all of them) Any ideas/hints? Appreciate it!

  • $\begingroup$ Is "$log$" the base-2 logarithm $log_2$? Is "$log$ $k =$$> n$" equivalent to "$k\ge q$"? $\endgroup$
    – fgrieu
    May 21, 2012 at 10:59
  • $\begingroup$ yes, $log_2$ and the second one is a typo, supposed to be $log$ $k = n$ (wasn't even a typo the block quote > messed it up.. $\endgroup$
    – Sup3rgnu
    May 21, 2012 at 13:06
  • $\begingroup$ If $log_2(q)=n$ and $log_2(k)=n$, we have $q=k$. Is that supposed to be $\lceil log_2(q)\rceil=\lceil log_2(k)\rceil=n$ or something on that tune? $\endgroup$
    – fgrieu
    May 21, 2012 at 13:19
  • $\begingroup$ If "the bit size of every prime factor of $k$ is bounded by $log_2(log_2(k))$" (give or take a few roundings to integer), then $k$ is exceptionally smooth; e.g. if $k$ has 1024 bits, all its factors are at most 1021. Is that meant? $\endgroup$
    – fgrieu
    May 21, 2012 at 13:30
  • 1
    $\begingroup$ The property that you can use to find $x$ is the smoothness of $k$ pointed out by fgrieu, as you can solve the discrete logarithm problem in very small subgroups of $\mathbb{F}_p^\times$ (your notation: $Z_p^*$) by inspection, and assemble those using the CRT. $\endgroup$
    – j.p.
    May 21, 2012 at 16:26

1 Answer 1


I'll give a sketch of the solution to a quite similar problem (that makes more sense to me). The purpose of this modified problem is to show that it is essential to take $g$ of order exactly $q$ in the given setup, as one otherwise gets an oracle returning $u^x$ given $u$ as in your problem. (I'll show the connection between both problems (yours and mine) at the end of my answer.)

Let $p = kq + 1$ and $q$ be primes such that $\log{q} \approx n$, $\log{k} \approx n$ and such that the bit size of every prime factor of $k$ is bounded by $\log{n}$. Let $g$ be an element of $Z^*_p$ of order $k'q = p-1$, where $k'\mid k$.

$x \in$ $Z_q$ is picked randomly and you get $g$ and $y = g^x$.

How would you go ahead to compute $x$ efficiently?

1) Write $k = \prod_i r_i$ as product of (pairwise coprime) prime powers r_i.

As $k$ has only small prime factors, you can find this factorization.

2) Define $g_i := g^\frac{kq}{r_i} = g^\frac{p-1}{r_i}$, and find its order $s_i$ in $Z^*_p$, which has to be a divisor of $r_i$.

3) Set $y_i := y^\frac{kq}{r_i} = y^\frac{p-1}{r_i} \in \langle g_i\rangle$ and determine $x_i \in \{0, 1, \dots, s_i-1\}$ with $g_i^{x_i} = y_i$.

As $s_i$ is the power of a small prime $p_i$, you can find $x_i$ by finding first $x_i \bmod p_i$, then $x_i \bmod p_i^2, \dots$ (please tell me, if you need a further hint for this).

4) Convince yourself that $x_i = x \bmod s_i$ for all $i$, and use the Chinese remainder theorem to find $x'$ with $x' = x \bmod \prod_i s_i$ (by definition $k'=\prod_i s_i$). As $x < q$ (we chose $x \in Z^*_p$), there are not many candidates $x' + l\cdot k'$ for $x$ as long as $\log k' \approx \log q$ (if $k' > q$ one has $x = x'$).

You can get from your problem to mine by finding a generator $u$ of $Z^*_p$ (you are able to find this generators as you know/can find the factorization of $p-1$), and applying once your oracle to obtain $u^x$ (with the nice extra property $k=k'$). I use then the relation between $g$ and $y$ to get a special oracle: $g_i$ corresponds to $u$, and $y_i$ to $u^x$.

Final remark: Instead of picking the random $x$ in $\{0, \dots, q-1\}$ one can could pick $x \in \{0, \dots, p-2\}$ to prevent anyone from finding $x \bmod q$, but giving away unnecessarily information about one's random source doesn't feel good and wastes resources...

  • $\begingroup$ Thanks man, I don't fully get it but def have a better picture now, thanks a lot appreciate it! $\endgroup$
    – Sup3rgnu
    May 25, 2012 at 20:26
  • $\begingroup$ @Sup3rgnu: You're welcome. If you have specific questions to any of the steps, you can leave a comment here, which I'll try to answer. $\endgroup$
    – j.p.
    May 26, 2012 at 11:59

Your Answer

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

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