無碰撞單向功能
假設整數分解的硬度，我正在玩一個我認為是無碰撞且不可逆的函式。不幸的是，我沒有像我想的那樣擅長數學，也不知道如何證明或反駁該函式是無碰撞的。到目前為止，我唯一的證據是對所有可能的輸入進行單元測試，這對於所有 2 字節組合都被證明是成功的，但顯然並不具體。
該算法迭代一系列位。它從 2 開始通過素數向上計數。對於輸入位中的每個連續的“1”位，指數計數器遞增。當遇到“0”位時，目前素數被取冪並組成執行輸出，指數計數器重置為 0，目前素數設置為下一個素數。
例如：
"11001101"被解釋為：
(2 ** 2) * (3 ** 0) * (5 ** 2) * (7 ** 1)假設輸出沒有被截斷，這個函式是否可以證明是無衝突的？
對於足夠大的輸入/輸出，該函式是否不可逆？
最後，如果輸出被修改（即截斷或旋轉），函式是否變得更難反轉？
針對答案進行編輯：讓我重新表述這個問題，以便更準確地了解我實際在做什麼。假設我們遍歷整數，從 0 開始並遞增 1。將每個整數轉換為其二進制形式並以上述方式對其進行處理。以這種方式產生的任何輸出值是否會發生衝突？
我正在回答我提出的問題。雖然 cygnusv 的答案對於我提出的想法是正確的，但這對我沒有幫助，因為我已經確定並解決了這個問題，但未能在我的問題中提出正確的算法。我不是說 cygnusv 是錯的。提供的答案非常正確，我給了+1。然而，還有更多的問題沒有得到解決。
右邊的零問題可以簡單地通過將“1”位或字元串長度附加到輸入字元串來解決。現在我已經在使用這個想法的玩具雜湊函式中這樣做了，但是它是在 unpack_factors 函式呼叫之前應用的，所以我忽略了它（這完全是我的錯）。
有了這個修復，該函式就獲得了我將僅稱為碰撞阻力的功能，該聲明僅基於通過提供輸入和記錄輸出進行的經驗測試，而不是理論猜想。
保理的硬度
關於“因式分解的硬度”，這實際上僅適用於 RSA 風格的組合，其中至少有一個因數在數軸上與 0 相距甚遠。
由於要測試大量素數，由大素數組成的因式分解很慢。如果一個數僅由小素數組成，即使是簡單的因式分解算法也可以有效地分解它。
例如，基本上解包所有 1 的任何位串都相當於 2 ** N，其中 N 是字元串的長度。即使是基本的因式分解算法也應該幾乎立即解決這個問題，或多或少不管輸入字元串有多長。
然而，在最後用一個 1 位解壓縮一個 0 位串將花費更長的時間，如果 0 的數量足夠長，可以將所討論的素數推到數軸右側足夠遠，那麼它將是“安全”，因為它永遠不會結束。然而，為了組成這樣一個數字，我們需要生成那個素數，這同樣耗時，因此不是我們可以依賴的情況。
輸出截斷和旋轉
現在，至於截斷輸出，這有一個有趣的效果。它不僅消除了碰撞阻力，而且使計算給定輸出的無限數量的原像變得微不足道。如果您只獲取最後 N 個字節的輸出，那麼任何解包和截斷以使最後 N 個字節相同的東西都是原像。
換句話說，給定一個輸出，你可以在它的左邊附加你想要的任何字節，分解它，並恢復一個有效的原像。雖然它確實使您無法確切知道是什麼輸入產生了輸出，但您可以找到它將駐留在其中的無限輸入集。
我認為旋轉輸出位會增加恢復的複雜性，當旋轉依賴於數據的量時，以這種方式旋轉的最大位數會增加，但我並不完全確定。除了可能產生碰撞之外，我想不出任何像截斷對旋轉的影響。
不，它不是無碰撞的。所有可能的 0 序列都產生相同的輸出：
0 --> (2 ** 0) = 1 00 --> (2 ** 0) * (3 ** 0) = 1 000 --> (2 ** 0) * (3 ** 0) * (5 ** 0) = 1 0000 --> (2 ** 0) * (3 ** 0) * (5 ** 0) * (7 ** 0) = 1其實可以看出 $ f(s) = f(s||0) $ , 對於每個位串 $ s $ .
這可以通過將指數初始化為 1 而不是 0 來輕鬆解決。
不管怎樣，恐怕你還沒有發現什麼新東西。算術基本定理指出，任何正整數都可以唯一地表示為素數的乘積：
$$ n = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k} = \prod_{i=1}^{k}p_i^{\alpha_i} $$ 你的想法基本上是一種將位串解釋為指數序列的方法 $ \alpha_1, \alpha_2, …, \alpha_{k} $ .
它也很容易反轉（撇開尾隨 0 的數量問題不談）。讓我們假設 $ f(s) = n $ . 如果 $ n $ 能被 2 整除，那麼第一個位 $ s $ 是 1。現在你除以 2，如果結果可以被 2 整除，那麼下一位 $ s $ 也是 1。重複直到它不能被 2 整除，並且你知道下一位是 0。以 3、5、7 等的可整性重複這個過程。
關於您添加的新問題：是的，存在衝突。
例如： $ f(1) = f(2) = f(4) = … = f(2^k) = 2 $
事實上，對於任何整數 $ n $ , 可以看出 $ f(n) = f(n\cdot 2^k) $ , 對於每個整數 $ k>0 $ ，這意味著對於每個整數都有無限的碰撞。