# Shor algorithm for discrete log and periodic function

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

• 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

## 1 Answer

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.