0
$\begingroup$

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

pic


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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .