How can we say there is absolute collision in Baby-Step Giant-Step attack for RSA? According to this paper, there is a Baby-Step Giant-Step attack for RSA encryption.
Consider the following Baby Step, Giant Step attack on RSA, with
public modulus $n$. Eve knows a plaintext $m$ and $a$ ciphertext $c$. She chooses $N^2 ≥ n$ and
makes two lists:
The first list is $c^j$
(mod n) for 0 ≤ j &lt; N.
The second list is $m.c^{−Nk}$ (mod n) for $ 0 ≤ k &lt; N $.
The mentioned paper solves this problem by the collision of these two lists.
But how can we say there's a absolute collision in these two lists?
But how can we say there's a absolute collision in these two lists?

Well, we know that $c^d \equiv m$ for some value $d &lt; n$, because of this, we have $d = Nk + j$ for some pair of integers $0 \le j &lt; N$ and $0 \le k &lt; N$.  We see that $c^j$ will appear somewhere in the first list, and $m \cdot c^{-Nk}$ will appear somewhere in the second list.
Since $c^{Nk + j} = m$, rearranging terms, we have $c^j = m \cdot c^{-Nk}$, and so those two terms will be the same.
That said, this is not a practical attack against RSA (and Coron et al never claimed it was).  The attack takes $O(\sqrt n)$ time, making it no more efficient than brute force factoring (and there are plenty of more efficient ways to break RSA than that).