哪些哈希函數相互正交？

Question

我對多級數據完整性檢查和糾正感興趣。在使用多個糾錯碼的情況下（它們可以是相同類型的碼中的兩個）。我的印象是，如果所使用的2個哈希碼彼此正交，那麼使用2個碼的系統將達到最大效果。

是否有哪些代碼與哪些代碼正交的列表？或者你是否需要使用相同的哈希函數，但使用不同的參數或用法？

我期望第一級ecc是一個reed-solomon代碼，但我實際上並沒有控制這個第一個函數，因此我不能使用具有改進功能的單個代碼。

請注意，我並不關心加密安全性。

編輯：這是不是

• When are hash functions orthogonal to each other?重複的，由於它基本上是問什麼的正交哈希函數的定義是。我想要哪些哈希函數是正交的例子。

Answer 1

我不確定甚至有可能枚舉所有正交散列函數。但是，您只是要求提供一些示例，因此我將盡力提供一些關於哪些屬性似乎導致正交散列函數的直覺。

從a related question，這兩個功能是彼此正交：

Domain: Reals --> Codomain: Reals 
f(x) = x + 1 
g(x) = x + 2 

這是一個相當明顯的情況。如果散列函數是（兩者）完美的散列函數（如這些函數），則更容易確定正交性。請注意，術語「完美」是指數學意義上的，而不是指這些應該用作散列函數。

對於滿足正交性要求的完美散列函數來說，這或多或少不重要。只要函數是injective，它們就是完美的散列函數，因此是正交的。類似的例子：

Domain: Integers --> Codomain: Integers 
f(x) = 2x 
g(x) = 3x 

在前面的情況下，這是一個單射函數而不是bijective，因爲在由域中的每個元素映射到陪域恰好一個要素是，但也有在該值域許多元素根本沒有映射。這些對於完美的哈希和正交性來說都是足夠的。 （請注意，如果Domain/Codomain是Reals，這將是一個雙射。）

非內射函數更難以分析。然而，它始終是這種情況，如果一個函數是單射，另一種是不，他們是不正交：

Domain: Reals --> Codomain: Reals 
f(x) = e^x // Injective -- every x produces a unique value 
g(x) = x^2 // Not injective -- every number other than 0 can be produced by two different x's 

所以一招因此知道一個函數是單射，另一種是不。但如果兩者都不是內射的呢？我目前不知道一般情況下的算法，它將決定這一點，而不是蠻力。

Domain: Naturals --> Codomain: Naturals 
j(x) = ceil(sqrt(x)) 
k(x) = ceil(x/2) 

既不函數是單射，在這種情況下，因爲兩個明顯的非射功能的存在的：ceil和abs具有受限域結合。 （實際上，大多數散列函數將不會有一個域比整數更加寬容。）測試出來的值將顯示j會有時k不會非唯一的結果，反之亦然：關於這些功能

j(1) = ceil(sqrt(1)) = ceil(1) = 1 
j(2) = ceil(sqrt(2)) = ceil(~1.41) = 2 
k(1) = ceil(x/2) = ceil(0.5) = 1 
k(2) = ceil(x/2) = ceil(1) = 1 

但什麼？

Domain: Integers --> Codomain: Reals 
m(x) = cos(x^3) % 117 
n(x) = ceil(e^x) 

在這種情況下，既沒有的功能是射（由於彈性模量和小區），但是做的時候，他們有衝突？更重要的是，對於x值的元組它們是否有碰撞？這些問題很難回答。我懷疑他們不是正交的，但沒有一個具體的反例，我不確定我能證明這一點。

當然，這些並不是您可能遇到的唯一散列函數。所以決定正交性的訣竅首先要看它們是否都是內射的。如果是這樣，它們是正交的。其次，看是否一個是內射的。如果是這樣，它們不是正交的。第三，看看你是否可以看到導致它們不是內射的函數片斷，看你能否確定它的週期或特殊情況（例如x = 0）並嘗試提出反例。第四，訪問math-stack-exchange，希望有人能告訴你他們在哪裏破壞了正交性，或者證明他們沒有。