The Uniqueness of Baby-step-Giant-step Algorithm on DLP

Question

The algorithm tells that, in the effort of solving $a^x \equiv b \text{ mod }N$:

1. Choose some $k \in \mathbb{N}$.

2. Create the baby list: $\{1,a,a^2,...,a^{k-1}\}$

3. Create the giant list: $\{ba^{-k},ba^{-2k},...,ba^{-rk}\}$ where $rk > N$.

Claim: If two lists have intersection, then this DLP has a solution.

$\textit{Proof:}$ Given that these two lists have an intersection, meaning that, for some $m,n$. \begin{align*} &a^n \equiv ba^{-mk} \text{ mod }N\\ & a^{mk+n} \equiv b \text{ mod }N\\ \end{align*} where $mk+n$ is $x$ as desired.

My question is, how do we know such solution is unique? or up to some equivalence? Is there any proof/counter-example for this?

Answer 1

It's unique modulo the multiplicative order of $a$ modulo $N$.

Suppose that there were two solutions: $$a^{n_1}\equiv ba^{-m_1k}\mod N;\quad\quad a^{n_1}\equiv ba^{-m_2k}\mod N$$ this would tells us that $$a^{m_1k+n_1}\equiv a^{m_2k+n_2}\pmod N$$ as both sides are $b\pmod N$. This then gives $$a^{m_1k+n_1-(m_2k+n_2)}\equiv 1\mod N$$ which can only be true if $\mathrm{ord}_N(a)|m_1k+n_1-(m_2j+n_2)$ which is the same as $$m_1k+N_1\equiv m_2+k_2\pmod{\mathrm{ord}_N(a)}.$$

An example of non-uniqueness is to take $N=15$, $a=7$ and $b=14$. Let's take $k=4$ and $r=4$. Our baby list is $$\{1,7,14,8\}$$ and our giant list is $$\{14,14,14,14\}$$ we get collisions $n=2$ with $m=1,2,3,4$ leading to possible values of $x=6,10,14,18$. All of these are equivalent modulo 4 which is the multiplicative order of 7 mod 15.