在彩虹表中查找的時間複雜度
Philippe Oechslin在著名的論文*Making a Faster Cryptanalytic Time-Memory Trade-Off (pdf) 中提到：*
因此，我們必須進行的計算總數是 $ \frac{t(t−1)}{2} $ . 這是經典方法的一半。確實，我們需要 $ t^2 $ 計算搜尋相應的 $ t $ 大小表 $ m × t $ .
但是，我的結果與他的不一致。這是我的想法：
如果我們將歸約函式的單個應用算作 0.5 計算，我們將不得不做 $ 0.5 + 1.5 + … + t-0.5 $ 在彩虹圖中查找時的最壞情況下的計算，即 $ \frac{t^2}{2} $ 計算，大於作者的 $ \frac{t(t-1)}{2} $ . 相比之下，原來的方法似乎要求 $ t(t-\frac{1}{2}) $ 計算，少於作者的 $ t^2 $ .
另外，作者的 $ \frac{t(t-1)}{2} $ 和 $ t^2 $ 給 $ 0 $ 和 $ 1 $ 分別當 $ t=1 $ ，這看起來很奇怪。
那麼誰錯了？
如果我們將一個歸約函式的單個應用算作 0.5 計算
$$ … $$
這似乎不是論文中的假設？我希望減少函式比雜湊/密碼花費更少的時間，因此完全折扣它們是一個足夠好的近似值。這給出了論文的價值。
如果你把它算作 0.5，那麼它需要 $ 0.5 + 2 + 3.5 +\dots + (t-1+0.5t) $ 而不是你所擁有的，因為在每一步你都為另一個雜湊/密碼和另一個減少添加 1.5 個工作。
相比之下，原來的方法似乎要求 $ t(t-\frac{1}{2}) $ 計算，少於作者的 $ t^2 $ .
這部分我不確定。我認為應該是 $ t(t-1) $ ，這與後面的文字相匹配，即彩虹表方法需要原始時間的一半。
一個 m * t 彩虹表需要 t(t-2)/2 次散列呼叫和相同數量的歸約函式。具有相同大小的 t 個表的經典方法需要兩倍的雜湊呼叫，但也需要兩倍的減少。回想一下，通過添加一個額外便宜的可逆函式，就像在彩虹表中一樣，不同的表是不同的。不同之處在於，傳統上我們對每個表使用不同的歸約，而在彩虹表中，我們對每列使用不同的歸約，但我們仍然為每個雜湊呼叫添加歸約。
還如前所述，減少通常非常便宜，通常帶有常數的異或會很好地工作，因此第 K 次減少功能只是與 k 異或。這很便宜，通常比散列呼叫便宜得多。我希望散列呼叫需要幾百個週期，而歸約函式需要 1 個或少數幾個，幾乎肯定至少要少一個數量級。