Baby-step-Giant-step算法在DLP上的唯一性
該算法表明，在解決問題的過程中 $ a^x \equiv b \text{ mod }N $ :
- 選擇一些 $ k \in \mathbb{N} $ .
- 創建寶貝列表： $ {1,a,a^2,…,a^{k-1}} $
- 創建巨型列表： $ {ba^{-k},ba^{-2k},…,ba^{-rk}} $ 在哪裡 $ rk > N $ .
聲明：如果兩個列表有交集，那麼這個 DLP 有一個解決方案。
$ \textit{Proof:} $ 鑑於這兩個列表有交集，這意味著，對於某些 $ m,n $ . $$ \begin{align*} &a^n \equiv ba^{-mk} \text{ mod }N\ & a^{mk+n} \equiv b \text{ mod }N\ \end{align*} $$ 在哪裡 $ mk+n $ 是 $ x $ 如預期的。
我的問題是，我們怎麼知道這樣的解決方案是唯一的？或達到某種等價？這有什麼證據/反例嗎？
它以乘法階為模是唯一的 $ a $ 取模 $ N $ .
假設有兩種解決方案： $$ a^{n_1}\equiv ba^{-m_1k}\mod N;\quad\quad a^{n_1}\equiv ba^{-m_2k}\mod N $$ 這會告訴我們 $$ a^{m_1k+n_1}\equiv a^{m_2k+n_2}\pmod N $$ 因為雙方都是 $ b\pmod N $ . 這然後給出 $$ a^{m_1k+n_1-(m_2k+n_2)}\equiv 1\mod N $$ 只有當 $ \mathrm{ord}_N(a)|m_1k+n_1-(m_2j+n_2) $ 這與 $$ m_1k+N_1\equiv m_2+k_2\pmod{\mathrm{ord}_N(a)}. $$
非唯一性的一個例子是 $ N=15 $ , $ a=7 $ 和 $ b=14 $ . 讓我們來 $ k=4 $ 和 $ r=4 $ . 我們的寶貝清單是 $$ {1,7,14,8} $$ 我們的大名單是 $$ {14,14,14,14} $$ 我們發生碰撞 $ n=2 $ 和 $ m=1,2,3,4 $ 導致可能的值 $ x=6,10,14,18 $ . 所有這些都是等價的模 4，即 7 mod 15 的乘法階。