BLAKE2 雜湊函式的執行時復雜度是多少？

假設您要計算blake2任意輸入的散列函式 $ n $ 字節。我想知道執行時，特別是：

1. 執行時間是否與輸入長度成線性關係，即執行時間blake2是否可以估計為O(n)？
2. 考慮到現代處理器（比如在 intel-i7 上）上的加密操作是如何優化的，landau 在這裡甚至是明智的嗎？

Blake2 接受（在任一變體中）輸入，在固定大小的塊中處理它，如果需要，用零填充最後一個塊到完整的塊大小。處理操作在恆定時間內發生（它需要恆定數量的周期，大 O 表示法沒有意義，因為輸入大小是固定的）。初始化和完成步驟也需要固定的時間。因此，整體操作需要 $ O(n) $ 時間。

Blake2 和許多其他流行的散列函式利用並行性。所以雖然理論上時間複雜度是 $ O(n) $ 但實際上你會在 2017 Intel Core i7-8700 上**看到 Blake2b類似的東西；**6×3200MHz；bitvise, supercop-20190910

資料來源：http ://bench.cr.yp.to/results-hash.html

如您所見，對於較小的輸入大小，循環不會線性擴展，但對於較大的大小，它幾乎可以。

PS：我列出了周期/字節的第三四分位數測量值。

引用自：https://crypto.stackexchange.com/questions/87855