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

youngeAn

11/20/23, 6:15 PM

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

Choose some $k \in \mathbb{N}$.
Create the baby list: $\{1,a,a^2,...,a^{k-1}\}$
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?

118

1 + 1

discrete-logarithm

diffie-hellman

kodlu

11/21/23, 12:57 PM

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.

Score:2

Crypto

Daniel S

11/20/23, 6:43 PM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.