1
$\begingroup$

I am about the following well known problem: Let $p$ is a prime number, $g$ is a generator of $(\mathbb{Z}/p\mathbb{Z})^\times$, $b \in (\mathbb{Z}/p\mathbb{Z})^\times$. Find $x$ - an integer such that $g^x = b \mod p$.

When I read about Shor algorithm for discrete log problem I always see the following function $$ f(x_1, x_2) = b^{x_1} a^{x_2} \mod p$$ and the task is to find the period of the function, i.e. $(\omega_1, \omega_2)$ such that $$ f(x_1, x_2) = f(x_1 + \omega_1, x_2 + \omega_2) $$.

My question is the following: why do we consider the complex function and don't consider the simplest one: $$ f(x_1) = b^{x_1} \mod p$$ If we can find the period of the function $\omega_1 < p - 1$ then $$g^{x \omega_1} = 1 \mod p$$ Thus from small Fermat theorem we have $$ x \omega_1 = 0 \mod p-1 $$ That can give the discrete log problem solution

$\endgroup$
  • $\begingroup$ I think that the problem of the last equation is that it has a lot of different solutions (i.e. there is not an unique solution), for instance $x=p-1$ will be the solution of that equation but it will not be correct solution for the discrete log problem $\endgroup$ – Ivan Dec 24 '17 at 22:07
  • $\begingroup$ Note that if $p$ is a safe-prime, then $\omega$ can either be 1,2 or $\frac{p-1}{2}$ (which is then also prime, this follows from Lagrange's theorem), neither of which should leak any information about the private key, because these values are public anyways. $\endgroup$ – SEJPM Dec 25 '17 at 8:49
1
$\begingroup$

Knowing the period of the second function cannot help you, because you already know it (at least for common Diffie-Hellman setups)!

First note that the period $\omega$ of $f(x_1)=b^{x_1}\bmod p$ is the order of $b$ because $f(0+\omega)=f(0)=1$ is implied by the general definition of a period $\forall x\in\mathbb Z:f(x)=f(x+\omega)$.

Now assume that $p$ is a safe prime (as is common for Diffie-Hellman). By Lagrange's theorem, we know that all multiplicative subgroups must have order $1,2,p-1$ or $\frac{p-1}{2}$ (the only divisors of $p-1$ by construction of $p$). Note that all these 4 values are trivially publicly computable.

Now notice that $f(x)$ generates a multiplicative subgroup of $\mathbb Z^*_p$ (similarly to how the generator works in DH). So this subgroup must have one of the 4 possible orders from above, which we already know. So we have learned nothing new by finding the order of the public key.

$\endgroup$

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.