# Shor's algorithm for discrete log and periodic function

I am wondering 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

• 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
– Ivan
Dec 24 '17 at 22:07
• 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.
– SEJPM
Dec 25 '17 at 8:49

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.