蒙哥馬利還原如何工作？
我想減少一個多精度整數 $ x $ 主要模組 $ p $ ， 非常快。執行傳統的歐幾里得除法僅計算模數是低效的，模數約簡是許多密碼學原語（如橢圓曲線密碼術）的核心。還有其他方法可以執行上述任務，例如 Barret 歸約等，但我想先了解一下 Montgomery 歸約及其特點，因為它具有實際意義。算法：
Input : Integer x, n, k Output : (2^(-k) * x) mod n 1. for t from 1 to k do 1.1 if x is odd then 1.1.1 x <- x+n 1.2 x <- x/2 2 Return x有限制 $ x $ 喜歡， $ 0 $ <= $ x $ < $ n^2 $ ， 並且， $ n $ 應該是奇怪的。我從中藉用上述算法的那本書陳述了兩個事實：
事實 1：將 n 添加到 x 不會改變殘差，因為實際上它會將商 ⌊x/n⌋ 添加 1。解釋這一點的另一種方法是 n （或 n 的倍數）與零模 n 一致。添加零不會改變殘差的值。
事實 2：如果 $ x $ 是偶數，然後除以二 $ Z $ 是一致的 $ x · 2^{−1} \mod n $ . 實際上，這是一個事實的應用，如果 x 可以被任何 $ k $ ∈ $ Z $ ，那麼 Z 中的除法將等於乘以 $ k^{−1} $ 模組 $ n $ .
我不明白Fact 2背後的含義。實際上，我很難理解作者是如何從正常算術超越模算術 mod n 的？為什麼是這樣的劃分 $ x $ 由兩個在 $ Z $ (整數) 等於乘以 $ 2^{-1} $ 通知 $ n $ . 畢竟 $ 2^{-1}\mod n $ 可以很容易地通過擴展歐幾里得算法計算：因為， $ n = 2q + r $ . 自從 $ n $ 很奇怪， $ r $ 應該 $ 1 $ . 因此，在轉置時，我們得到： $ n - 2q = 1 $ . 如果我們把前面的方程取模 $ n $ ，我們得到 $ -q $ 作為乘法逆 $ 2 $ wrt mod n。
如果我能很好地解釋蒙哥馬利減少的工作原理，那將不勝感激。為什麼我們不斷添加 $ n $ 至 $ x $ ， 如果 $ x $ 奇怪嗎？
我的理解中缺少一些非常清晰的內容！蒙哥馬利乘法減法背後的堅實原則是什麼？因為，我主要來自程式背景，在這方面我似乎缺乏一些數學知識。
每一個幫助將不勝感激！
1985 年，蒙哥馬利引入了一種新的巧妙方式來表示數字 $ \mathbb{Z}/n \mathbb{Z} $ 這樣算術，尤其是模乘法變得更容易。
我們需要模數 $ n $ 我們正在工作和一個整數 $ r $ 這樣 $ \gcd(r,n) =1 $ 和 $ r>n $
定義：蒙哥馬利表示 $ x \in [0,n-1] $ 是 $ \bar{x} = (xr) \bmod n $
定義：蒙哥馬利減少 $ u \in [0,rn-1] $ 是 $ Redc(u) = (ur^{-1}) \bmod n $ . 這也被稱為 $ n $ - 殘留物 $ r $ . 確實，可以證明這組$$ {i\cdot r \bmod n | 0 \leq i \leq n} $$是一個完整的殘留系統。
在密碼學中，我們通常使用素數模數，因此我們可以選擇 $ r = 2^k $ . 在這種情況下 $ \gcd(r,n) = \gcd(2^k,n) = 1 $ 很滿意。
事實 1：
因為我們正在模數工作 $ n $ ，這是一個基本的結果。
事實 2：如果 $ x $ 是偶數，然後除以二 $ \mathbb{Z} $ 是一致的 $ x\cdot 2^{−1} \bmod n $ . 實際上，這是一個事實的應用，如果 $ x $ 可以被任何整除 $ k \in \mathbb{Z} $ ，然後除以 $ \mathbb{Z} $ 將等於乘以 $ k^{−1} \bmod n $ .
他們試圖說的是
- 讓 $ k $ 劃分 $ x $ 然後 $ u \cdot k = x $ 取模數 $ n $ 兩側。 $$ u \cdot k = x \bmod n $$自從 $ n $ 是素數 $ k^{-1} $ 模數存在 $ n $ 這可以通過擴展歐幾里得算法找到。對於蒙哥馬利，這僅需要一次 $ r $ . 現在我們有了；
$$ u \cdot k \cdot k^{-1} = x \cdot k^{-1} \bmod n $$
$$ u = x \cdot k^{-1} \bmod n $$
1.2 x <- x/2
當。。。的時候 $ r = 2^k $ 這通常由移位操作執行。這是蒙哥馬利的詭計。審判科轉為輪班制。
x = x >> 2蒙哥馬利乘法減法背後的可靠原則是什麼？
Montgomery Reduction這是維基百科的版本。
input: Integers r and n with gcd(r, n) = 1, Integer n′ in [0, r − 1] such that nn′ ≡ −1 mod r, Integer T in the range [0, rn − 1] output: Integer s in the range [0, n − 1] such that s ≡ Tr^−1 mod n m = ((T mod r)n′) mod r t = (T + mn) / r if t ≥ n then return t − n else return t現在，優勢很明顯。自從 $ r= 2^{k} $ 劃分和 $ \bmod $ 通過移位或掩蔽操作很便宜。
這 $ n’ $ 定義為 $ rr^{-1} -n n’ =1 $
正確性可見
- 觀察如果 $ m = (( T \bmod r )n^{’}) \bmod r $ 然後 $ T + mn $ 可以被 $ r $ .
$$ T + mn \equiv T + (((T \bmod r)n’) \bmod r)n \equiv T + T n’ n \equiv T - T \equiv 0 \pmod{R} $$那里為 $ t $ 是整數，不是浮點數。
然後輸出是 $ y $ 或者 $ t-n $ （記住事實1）。現在讓我們看看為什麼輸出是 $ Tr^{-1} $ . 我們再次使用我們所知道的
$$ t \equiv ( T + mn )r^{-1} \equiv Tr^{-1} + (mr^{-1})n \equiv Tr^{-1} \pmod{n)} $$
因此，輸出具有我們想要的正確殘差。
為什麼要下沉？我們需要跟踪 $ t $ 的大小。
- $ m \in [0,r-1] $
- $ T+mn $ 然後介於 $ 0 $ 和 $ (rn-1) + (r-1)n < 2rn $ . 由於除以 $ r $ 然後 $ 0 \leq t \leq 2n-1 $ . 單次減法可以減少 $ t $ 到所需的範圍內。
蒙哥馬利產品
我們將定義一個非常強大的函式。記住 $ \bar{a} = ar \bmod n $
- $ MonPro(\bar{a},\bar{b},r,n) $
//輸出 $ t = MonPro(\bar{a},\bar{b},r,n) = \bar{a}\bar{b}r^{-1} \pmod{n} $
- $ T = \bar{a}\bar{b} $
- $ m = T n’ \bmod r $
- $ t = (T+mn)/r $
- 如果 $ t \geq n $ $ \text{return}(t-n) $
- $ \text{return}(t) $
讓我們簡化 $ MonPro(\bar{a},\bar{b},r,n) $ 至 $ MonPro(\bar{a},\bar{b}) $ 因為我們保持它們不變並且 $ r^{} $ 可以在運算前計算為常數。
- 如果我們呼叫會發生什麼： $ MonPro(\bar{a},1) $ ?
$$ MonPro(\bar{a},1) = (a r) \cdot 1 \cdot r^{-1} = a \pmod{n} $$
- 如果我們呼叫會發生什麼： $ MonPro(\bar{a},b) $ ?
$$ MonPro(\bar{a},b) = (a r) \cdot b \cdot r^{-1} = a \cdot b\pmod{n} $$
- 如果我們呼叫會發生什麼： $ MonPro(a,r) $ ?
$$ MonPro(a,1) = a \cdot 1 \cdot r^{-1} = a r^{-1} \pmod{n} $$