模運算功能的背景
我正在研究這個功能：
$ a := ((b\cdot c) \bmod k) - (b \cdot c)/k $
在哪裡 $ / $ 表示整數除法。
我注意到兩件事：
- 相當於將 a·b 相乘，然後從低位減去高位（在除以 k 的基數中）
- 它是完全線性的，可以在恆定時間內倒置（即給定 a 和 b，確定 c）。
這個功能有什麼背景嗎？有沒有人討論它，或類似的功能？它屬於一個已知的家庭嗎？它有任何已知的應用嗎？
簡而言之：我在哪裡可以找到更多關於它的資訊？我對密碼學的應用程序特別感興趣。
正如 DW 所發現的，這實際上是推薦的 IDEA 實現的一部分。IDEA 使用 $ a\cdot b \bmod (2^{16}+1) $ , 特殊情況下的處理 $ 0 $ 作為 $ 2^{16} $ . 來自應用密碼學手冊，註釋 7.016：
注意（實現 $ ab \bmod 2^{n}+1 $ ) 乘法 $ \bmod 2^{16}+1 $ 可以有效地實現如下，對於 $ 0 \leq a, b \leq 2^{16} $ （參見§14.3.4）。讓 $ c = ab = c_0·2^{32} +c_H·2^{16} +c_L $ ， 在哪裡 $ c_0 \in { 0, 1} $ 和 $ 0 \leq c_L, c_H < 2^{16} $ . 計算 $ c’ = c \bmod (2^{16} + 1) $ ，首先獲得 $ c_L $ 和 $ c_H $ 通過標準乘法。為了 $ a = b = 2^{16} $ ， 注意 $ c_0 = 1 $ , $ c_L = c_H = 0 $ ， 和 $ c’ = (−1)(−1) = 1 $ ， 自從 $ 2^{16} \equiv −1 \mod (2^{16}+1) $ ; 除此以外， $ c_0 = 0 $ . 最後， $ c’ = c_L − c_H + c_0 $ 如果 $ c_L \geq c_H $ ， 儘管 $ c’ = c_L − c_H + (2^{16} + 1) $ 如果 $ c_L < c_H $ （自那時候起 $ −2^{16} < c_L − c_H < 0 $ ).
這是完全一致的。
這當然給我留下了一些更大的問題，例如只有線性操作的 IDEA 是如何安全的，以及我可以在哪裡閱讀更多關於它的資訊（網上很少有深入的討論），但這些是針對不同的文章的。另一件有趣的事情是，與其他具有常量表的密碼不同，查看二進制程式碼並辨識 IDEA 並非易事。你可以掃描 $ 2^{16}+1 $ ，但這並不像查找 md5 表那樣確定。
乍一看，它看起來不像是一個有趣的函式。如果我們定義：
$$ f(b, c) = (b\cdot c)%k - (b\cdot c)/k $$ 那麼我們總是有：
$$ f(b, c) \equiv bc \mod k+1 $$ 換句話說，這在很大程度上只是進行模乘的一種奇怪方式。當然， $ f(b, c) $ 並不總是 $ (bc) % (k+1) $ ; 有時它是負面的。乍一看，我沒有看到任何有趣的模式。