# Discrete Logarithm Problem as Period finding of a function

The discrete logarithm problem (DLP) : Find $$b$$ knowing $$s,a$$ and $$p$$ such that $$b=a^s\mod p$$ where $$p$$ is a prime number and $$a$$ is a generator of the group defined by $$p$$.

It is stated that the discrete logarithm problem can be solved as an instance of period finding for the function $$f(x_1,x_2)=a^{sx_1+x_2}\mod p$$ through the observation that $$f$$ is periodic with period $$(l,-ls)$$ for each integer $$l$$ and $$b=a^s$$

How do we justify this ?

Screenshot of the original context from the reference, Page 238, Quantum Computation and Quantum Information by Nielsen and Chuang

In a similar argument,

The order of an element $$a$$ in the group $$(\mathcal{Z}_p^*,.)$$ is the smallest positive integer $$r$$ such that $$a^r=1\pmod p$$.

The order finding can be seen as an instance of period finding for the function $$f_a(s)=a^s\mod p$$, since the period of the function is exactly the order, i.e., $$f_a(s+r)=a^{s+r}\mod p=a^sa^r\mod p=a^s\mod p=f(s)$$

Can I extend this somehow to understand the approach on the DLP problem ?

Note : This is the approach we use as a starting point to solve DLP in quantum computing thereby allows to crack the Diffie-Hellman key exchange cipher.

The DLP is that, let $$a$$ be a generator of a group $$\mathbb{G}$$ which we can choose as $$(\mathbb{Z}_p^*,.)$$ where $$p$$ is a prime number, find the least positive integer value of $$s$$ such that $$b=a^s\mod p\in(\mathbb{Z}_p^*,.)$$
Note : $$(\mathbb{Z}_p^*,.)$$ is a cyclic group for any prime number $$p$$
Consider the function $$f(x_1,x_2)=b^{x_1}a^{x_2}\mod p$$ which has a 2-tuple period $$(t_1,t_2)$$ such that $$f(x_1+t_1,x_2+t_2)=f(x_1,x_2)$$. So, $$f(x_1+t_1,x_2+t_2)=f(x_1,x_2)\implies b^{x_1+t_1}a^{x_2+t_2}\mod p=b^{x_1}a^{x_2}\mod p\\ b^{t_1}a^{t_2}\mod p=(a^s)^{t_1}a^{t_2}\mod p=(a)^{st_1}a^{t_2}\mod p=a^{st_1+t_2}\mod p=1\\$$ $$\implies st_1+t_2=kr\text{ for some integer }k\\$$ where $$r$$ is the order of the element $$a\in(\mathbb{Z}_p^*,.)$$ such that $$a^r\mod p=1$$. Let's take $$k=0$$ then $$st_1+t_2=0\implies \boxed{s=-t_2/t_1}$$ $$f(x_1,x_2)=b^{x_1}a^{x_2}\mod p=(a^s)^{x_1}a^{x_2}\mod p=a^{sx_1+x_2}\mod p$$ Therefore, determining the 2-tuple period of the function $$f(x_1,x_2)=b^{x_1}a^{x_2}\mod p=a^{sx_1+x_2}\mod p$$ allows us to find $$s$$, thereby solving the discrete logarithm problem.