1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – kodlu
    Nov 21, 2022 at 12:57

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.