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

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?

• Please delete the duplicate of this question on math.stackexchange since it's been answered here. Also, it is good practice to accept a satisfactory answer. Nov 21, 2022 at 12:57

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.